Container method: Difference between revisions

Revision as of 02:27, 21 March 2024

Latest revision as of 02:43, 28 May 2025

(4 intermediate revisions by 3 users not shown)

Line 9:

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 |doi-access=free }}</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> 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> and study a variety of other enumeration problems<ref>{{Citation|last=Sapozhenko|first=Alexander|title=Systems of Containers and Enumeration Problems|date=2005|url=http://dx.doi.org/10.1007/11571155_1|work=Stochastic Algorithms: Foundations and Applications|series=Lecture Notes in Computer Science |volume=3777 |pages=1–13|place=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|doi=10.1007/11571155_1 |isbn=978-3-540-29498-6|access-date=2022-02-13|url-access=subscription}}</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 Mathematicae |date=2015 |volume=201 |issue=3 |pages=925–992|doi=10.1007/s00222-014-0562-8 |arxiv=1204.6595 |bibcode=2015InMat.201..925S |s2cid=119253715 }}</ref> and Balogh, Morris, and Samotij<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=669–709|doi= 10.1090/S0894-0347-2014-00816-X |s2cid= 15244650 |doi-access=free |arxiv=1204.6530 }}</ref> in 2015, inspired by a variety of previous related work.

Line 69:

:<math>i(G, r) \le {n \choose q}{R \choose r - q}.</math>

'''Lemma 2:''' Let <math>G</math> be a graph on <math>n</math> vertices and assume that an integer <math>q</math> and reals <math>R, D</math> are chosen such that <math>n \le R+ qD</math>. If all subsets <math>U</math> of at least <math>R</math> vertices have at least <math>D|U|/2</math> edges, then there is a collection <math>\mathcal{F}</math> of subsets of <math>q</math> vertices ("fingerprints") and a deterministic function <math>f:\colon \mathcal{C} \rightarrow \mathcal{P}(V(G))</math>, so that for every independent set <math>I \subset V(G)</math>, there is <math>S \in \mathcal{F}</math> such that <math>S \subset I \subset f(S) \cup S</math>.

==Hypergraph container lemma==

Line 79:

===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=669–709|doi= 10.1090/S0894-0347-2014-00816-X |s2cid= 15244650 |doi-access=free |arxiv=1204.6530 }}</ref>

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:\colon \mathcal{P}(V(H)) \rightarrow \mathcal{C}</math> such that

* for every <math>I \in \mathcal{I}(H)</math> there exists <math>S \subset I</math> with <math>|S|\le(k-1)b</math> and <math>I\subset f(S)</math>.

* <math>|C| \le |V(H)| - \delta r</math> for every <math>C \in \mathcal{C}</math> and <math>\delta = 2^{-k(k+1)}</math>.

Line 98:

====Sum-free sets====

A set <math>A</math> of elements of an [[abelian group]] is called ''sum-free'' if there are no <math>x,y,z\in A</math> satisfying <math>x+y=z</math>. We will show that there are at most <math>2^{(1/2+o(1))n}</math> sum-free subsets of <math>[n]:=\{1,2,\ldots , n\}</math>.

This will follow from our above bounds on the number of independent sets in a regular graph. To see this, we will need to construct an auxiliary graph. We first observe that up to lower order terms, we can restrict our focus to sum-free sets with at least <math>n^{2/3}</math> elements smaller than <math>n/2</math> (since the number of subsets in the complement of this is at most <math> (n/2)^{n^{2/3}} 2^{n/2 + 1}</math>).

Line 114:

We can construct an auxiliary {{math|''3''}}-uniform hypergraph {{math|''H''}} with vertex set <math>V(H) = E(K_n)</math> and edge set <math>E(H) = \{\{e_1, e_2, e_3\} \subset E(K_n) = V(H) \mid e_1, e_2, e_3 \text{ form a triangle}\}</math>. This hypergraph "encodes" triangles in the sense that the family of triangle-free graphs on <math>n</math> vertices is exactly the collection of independent sets of this hypergraph, <math>\mathcal{I}(H)</math>.

The above hypergraph has a nice [[degree distribution]]: each edge of <math>K_n</math>, and thus vertex in <math>V(H)</math> is contained in exactly <math>n-2</math> triangles and each pair of elements in <math>V(H)</math> is contained in at most 1 triangle. Therefore, applying the hypergraph container lemma (iteratively), we are able to show that there is a family of <math>n^{O(n^{3/2})}</math> containers that each contain few triangles that contain every triangle-free graph/independent set of the hypergraph.

====Upper bound on the number of triangle-free graphs====

Line 127:

'''Theorem:''' For all <math>\epsilon > 0</math>, there exists <math>C>0</math> such that the following holds. For each positive integer {{math|''n''}}, there exists a collection <math>\mathcal{G}</math> of graphs on {{math|''n''}} vertices with <math>|\mathcal{G}| \le n^{Cn^{3/2}}</math> such that

* each <math>G \in \mathcal{G}</math> has fewer than <math>\epsilon n^3</math> triangles,

* each [[triangle-free graph]] on <math>n</math> vertices is contained in some <math>G \in \mathcal{G}</math>.

'''Proof:''' Consider the hypergraph <math>H</math> defined above. As observed informally earlier, the hypergraph satisfies <math>|V(H)| = {n \choose 2}, \Delta_2(H) = 1, d(v) = n - 2</math> for every <math>v \in V(H)</math>. Therefore, we can apply the above Lemma to <math>H</math> with <math>c=1</math> to find some collection <math>\mathcal{C}</math> of <math>n^{O(n^{3/2})}</math> subsets of <math>E(K_n)</math> (i.e. graphs on <math>n</math> vertices) such that