Content deleted Content added
Declining submission: neo - Submission is about a neologism not yet shown to meet notability guidelines (AFCH 0.9.1) |
Citation bot (talk | contribs) Alter: journal, pages. Add: s2cid, bibcode, arxiv, issue, isbn, doi. Formatted dashes. | Use this bot. Report bugs. | Suggested by RoanokeVirginia | Category:AfC submissions on science, mathematics and engineering | #UCB_Category 159/431 |
||
Line 13:
One of the foundational problems of extremal graph theory, dating to work of Mantel in 1907 and [[Turán's theorem|Turán]] from the 1940s, asks to characterize those graphs that do not contain a copy of some fixed [[forbidden subgraph problem|forbidden]] {{math|''H''}} as a subgraph. In a different ___domain, one of the motivating questions in additive combinatorics is understanding how large a set of integers can be without containing a {{math|''k''}}-term [[arithmetic progression]], with upper bounds on this size given by [[Roth's theorem on arithmetic progressions|Roth]] (<math>k=3</math>) and [[Szemerédi's theorem|Szemerédi]] (general {{math|''k''}}).
The method of containers (in graphs) was initially pioneered by Kleitman and Winston in 1980, who bounded the number of lattices.<ref>{{cite journal |last1=Kleitman |first1= Daniel |last2=Winston |first2=Kenneth |title=The asymptotic number of lattices |journal=Annals of Discrete Mathematics |date=1980 |volume=6 |pages=243–249|doi= 10.1016/S0167-5060(08)70708-8 |isbn= 9780444860484 }}</ref> and graphs without 4-cycles<ref>{{cite journal |last1=Kleitman |first1= Daniel |last2=Winston |first2=Kenneth |title=On the number of graphs without 4-cycles |journal=Discrete Mathematics |date=1982 |volume=31 |issue= 2 |pages=167–172|doi= 10.1016/0012-365X(82)90204-7 }}</ref>. Container-style lemmas were independently developed by multiple mathematicians in different contexts, notably including Sapozhenko, who initially used this approach in 2002-2003 to enumerate independent sets in [[regular graphs]]<ref>{{cite journal |last1=Sapozhenko |first1=Alexander |title=The Cameron-Erdos conjecture |journal=Doklady Akademii Nauk |date=2003 |volume=393 |pages=749–752}}</ref> and sum-free sets in abelian groups<ref>{{cite journal |last1=Sapozhenko |first1=Alexander |title=Asymptotics for the number of sum-free sets in Abelian groups |journal=Doklady Akademii Nauk |date=2002 |volume=383 |pages=454–458}}</ref>.
A generalization of these ideas to a hypergraph container lemma was devised independently by Saxton and Thomason<ref>{{cite journal |last1=Saxton |first1=David |last2=Thomason |first2=Andrew |title=Hypergraph containers |journal=Inventiones
==Main idea and informal statement==
Line 37:
==Kleitman-Winston algorithm==
We first describe a method for showing strong upper bounds on the number of independent sets in a graph; this exposition adapted from a survey of Samotij about the graph container method.<ref>{{cite journal |last1=Samotij |first1= Wojciech |title=Counting independent sets in graphs |journal=European Journal of Combinatorics |date=2015 |volume=48 |pages=5–18|doi= 10.1016/j.ejc.2015.02.005 |s2cid= 15850625 }}</ref>
===Notation===
Line 83:
===Statement===
We state the version of this lemma found in a work of Balogh, Morris, Samotij, and Saxton<ref>{{cite journal |last1=Balogh |first1= József |last2=Morris |first2=Robert|last3=Samotij|first3=Wojciech |title=Independent sets in hypergraphs |journal=Journal of the American Mathematical Society |date=2015 |volume=28 |issue= 3 |pages=
Let <math>\mathcal{H}</math> be a <math>k</math>-uniform hypergraph and suppose that for every <math>l \in \{1,2,\ldots, k\}</math> and some <math>b, r \in \mathbb{N}</math>, we have that <math>\Delta_l(H) \le \left( \frac{b}{|V(H)|} \right)^{l-1} \frac{|E(H)|}{r}</math>. Then, there is a collection <math>\mathcal{C} \subset \mathcal{P}(V(H))</math> and a function <math>f: \mathcal{P}(V(H)) \rightarrow \mathcal{C}</math> such that
Line 111:
===Triangle-free graphs===
We give an illustration of using the hypergraph container lemma to answer an enumerative question by giving an asymptotically tight upper bound on the number of triangle-free graphs with <math>n</math> vertices.<ref>{{cite journal |last1=Balogh |first1= József |last2=Morris |first2=Robert|last3=Samotij|first3=Wojciech |title=The method of hypergraph containers |journal=Proceedings of the International Congress of Mathematicians: Rio de Janeiro |date=2018|arxiv= 1801.04584 }}</ref>
====Informal statement====
| |||