Content deleted Content added
Submitting using AfC-submit-wizard |
m Open access bot: url-access updated in citation with #oabot. |
||
| (24 intermediate revisions by 12 users not shown) | |||
Line 1:
{{Short description|Method in combinatorics}}
The '''method of (hypergraph) containers''' is a powerful tool that can help characterize the typical structure and/or answer extremal questions about families of discrete objects with a prescribed set of local constraints. Such questions arise naturally in [[extremal graph theory]], [[additive combinatorics]], [[discrete geometry]], [[coding theory]], and [[Ramsey theory]]; they include some of the most classical problems in the associated fields.
These problems can be expressed as questions of the following form: given a [[hypergraph]] {{math|''H''}} on finite vertex set {{math|''V''}} with edge set {{math|''E''}} (i.e. a collection of subsets of {{math|''V''}} with some size constraints), what can we say about the [[independent set (graph theory)|independent sets]] of {{math|''H''}} (i.e. those subsets of {{math|''V''}} that contain no element of {{math|''E''}})? The hypergraph container lemma provides a method for tackling such questions.
Line 13 ⟶ 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>
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==
Many problems in combinatorics can be recast as questions about independent sets in graphs and hypergraphs. For example, suppose we wish to understand subsets of integers {{math|''1''}} to {{math|''n''}}, which we denote by <math>[n]</math> that lack a {{math|''k''}}-term arithmetic progression. These sets are exactly the independent sets in the {{math|''k''}}-uniform hypergraph <math> H = (\{1,2,\ldots,n\}, E) </math>, where {{math|''E''}} is the collection of all {{math|''k''}}-term arithmetic progressions in <math> \{1,2,\ldots,n\} </math>.
In the above (and many other) instances, there are usually two natural classes of problems posed about a hypergraph {{math|''H''}}:
* What is the size of a maximum independent set in {{math|''H''}}? What does the collection of maximum-sized independent sets in {{math|''H''}} look like?
* How
These problems are connected by a simple observation. Let <math>\alpha(H)</math> be the size of a largest independent set of {{math|''H''}} and suppose <math>H</math> has <math>i(H)</math> independent sets. Then,
:<math>2^{\alpha(H)} \le i(H) \le \sum_{r = 0}^{\alpha(H)} {|V(H)| \choose r},</math>
Line 34 ⟶ 30:
The name container alludes to this last condition. Such containers often provide an effective approach to characterizing the family of independent sets (subsets of the containers) and to enumerating the independent sets of a hypergraph (by simply considering all possible subsets of a container).
The hypergraph container lemma achieves the above container decomposition in two pieces. It constructs a deterministic function {{math|''f''}}. Then, it provides an algorithm that extracts from each independent set {{math|''I''}} in hypergraph {{math|''H''}}, a relatively small collection of vertices <math>S \subset I</math>, called a ''fingerprint,'' with the property that <math> S \subset I \subset S \cup f(S)</math>. Then, the containers are the collection of sets <math>S \cup f(S)</math> that arise in the above process, and the small size of the fingerprints provides good control on the number of such container sets.
==
We first describe a method for showing strong upper bounds on the number of independent sets in a graph; this exposition is adapted from a survey of Samotij
===Notation===
Line 45 ⟶ 41:
* The ''max-degree ordering'' of a vertex subset <math> A \subset V</math> is the ordering of the vertices in {{math|''A''}} by their degree in the [[induced subgraph]] <math>G[A]</math>.
===Kleitman-Winston algorithm===
The following algorithm gives a small "fingerprint" for every independent set in a graph and a deterministic function of the fingerprint to construct a not-too-large subset that contains the entire independent set
Line 57 ⟶ 53:
===Analysis===
By construction, the output of the above algorithm has property that <math>\{v_{j_1}, \ldots, v_{j_q}\} \subset I \subset \{v_{j_1}, \ldots, v_{j_q}\} \cup (A \cap I)</math>, noting that <math>A \cap I</math> is a vertex subset that is completely determined by <math>\{j_1, \ldots, j_q\}</math> and not otherwise a function of <math>I</math>. To emphasize this we will write <math>A
This suggests that <math>S</math> might be a good choice of a ''fingerprint'' and <math>S(j_1, \ldots j_q) \cup A(j_1, \ldots, j_q)</math> a good choice for a ''container''. More precisely, we can bound the number of independent sets of <math>G</math> of some size <math>r \ge q</math> as a sum over output sequences <math>(j_1, \ldots j_q)</math>
Line 73 ⟶ 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
==Hypergraph container lemma==
Line 83 ⟶ 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=
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
* 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 102 ⟶ 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 111 ⟶ 107:
===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====
Line 118 ⟶ 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 131 ⟶ 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
Line 146 ⟶ 142:
== References ==
{{reflist}}
[[Category:Extremal graph theory]]
[[Category:Hypergraphs]]
[[Category:Additive combinatorics]]
| |||