Independent sets in hypergraphs

By Jozsef Balogh, Robert Morris, Wojciech Samotij. 2012

446 citations recorded by the source corpus.

Many important theorems and conjectures in combinatorics, such as the the- orem of Szemeredi on arithmetic progressions and the Erd˝os-Stone Theorem in extremal graph theory, can be phrased as statements about families of independent sets in certain uniform hypergraphs. In recent years, an important trend in the area has been to extend such classical results to the so-called 'sparse random setting'. This line of research has recently culminated in the breakthroughs of Conlon and Gowers and of Schacht, who de- veloped general tools for solving problems of this type. Although these two papers solved very similar sets of longstanding open problems, the methods used are very different from one another and have different strengths and weaknesses. In this paper, we provide a third, completely different approach to proving extremal and structural results in sparse random sets that also yields their natural 'counting' coun- terparts. We give a structural characterization of the independent sets in a large class of uniform hypergraphs by showing that every independent set is almost contained in one of a small number of relatively sparse sets. We then derive many interesting results as fairly straightforward consequences of this abstract theorem. In particular, we prove the well- known conjecture of Kohayakawa, Luczak, and Rodl, a probabilistic embedding lemma for sparse graphs, for all 2-balanced graphs. We also give alternative proofs of many of the results of Conlon and Gowers and Schacht, such as sparse random versions of Szemeredi's theorem, the Erd˝os-Stone Theorem and the Erd˝os-Simonovits Stability Theorem, and ob- tain their natural 'counting' versions, which in some cases are considerably stronger. We also obtain new results, such as a sparse version of the Erd˝os-Frankl-Rodl Theorem on the number of H-free graphs and, as a consequence of the K LR conjecture, we extend a re- sult of Rodl and Rucinski on Ramsey properties in sparse random graphs to the general, non-symmetric setting. Similar results have been discovered independently by Saxton and Thomason.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/2c2aec489b1090fad473d557665aeb9016748de0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Diagonal Ramsey via effective quasirandomness (2020, methodology): “eeded [11] (here tow means taking an exponential tower of 2’s of the speciﬁed length). Much attention has been given to generalizing this result to hypergraphs (e.g. [17, 12]) and sparse graphs (e.g. [10, 1, 3, 19, 6, 7]) in connection with extremal graph theory and additive combinatorics. However, ”
The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹 (2016, methodology): “This can be seen by adapting a construction from [28] as follows.”
The asymptotics of r(4,t) (2023, methodology): “…following is found in Kohayakawa, Lee, R¨odl and Samotij [35], and is a special case of the method of containers due to Balogh, Morris and Samotij [5] and Saxton and Thomason [48]: Proposition 4 Let G be a graph on n vertices, and let r, R ∈ N , and α ∈ [0 , 1] satisfy: and, for every subset Then…”
Combinatorial theorems in sparse random sets (2010, background): “lrThe full KŁR conjecture was subsequently established by Balogh, Morris and Samotij [1] and by Saxton and Thomason [54] (see also [5]).”
The number of $C_{2l}$-free graphs (2013, methodology): “s that H also satisﬁes condition (b) of the theorem, as required. 4. Hypergraph containers In this section we recall the basic deﬁnitions relating to hypergraph containers, and state the theorem from [5, 49] that we will use in order to deduce Theorems 1.1 and 1.2 from Theorem 1.5. In order to do so”
On the average size of independent sets in triangle-free graphs (2016, methodology): “ lower bounding the independence number of Kr-free graphs and that of Alon [2] in lower bounding the independence number of graphs of average degree d in which neighborhoods are r-colorable. See also [16] for a recent application of this method to hypergraphs. However, here we use the full power of ”
The existence of designs via iterative absorption (2016, background): “[25]) to obtain arbitrarily large r-graphs Hn on n vertices with α(Hn) < q and ∆(Hn) ≤ n/N ≤ brn log q/qr−1.”
THE METHOD OF HYPERGRAPH CONTAINERS (2018, methodology): “Although the hypergraph container lemma (see Section 3) was discovered only recently (see Balogh, Morris, and Samotij [2015] and Saxton and Thomason [2015]), several theorems of the same flavour (though often in very specific settings) appeared much earlier in the literature. The earliest container-”
Extremal problems for cycles in graphs (2016, methodology): “The development of new techniques of Balogh, Morris and Samotij [4] and Saxton and Thomason [114], sometimes referred to as the method of containers, has led to the following theorem of Morris and Saxton [99]: Theorem 10.”