Container method: Difference between revisions

Revision as of 17:23, 8 December 2024

Revision as of 06:34, 15 May 2025

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