Independent sets in hypergraphs

Abstract

Many important theorems and conjectures in combinatorics, such as the theorem of Szemerédi on arithmetic progressions and the Erdős–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 developed general tools for solving problems of this type. Although these two articles 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 article, we provide a third, completely different, approach to proving extremal and structural results in sparse random sets that also yields their natural ‘counting’ counterparts. 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, Łuczak, and Rödl, a probabilistic embedding lemma for sparse graphs. We also give alternative proofs of many of the results of Conlon and Gowers and of Schacht, such as sparse random versions of Szemerédi’s theorem, the Erdős–Stone Theorem, and the Erdős–Simonovits Stability Theorem, and obtain their natural ‘counting’ versions, which in some cases are considerably stronger. For example, we show that for each positive <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="beta"> <mml:semantics> <mml:mi> β </mml:mi> <mml:annotation encoding="application/x-tex">\beta</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , there are at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartBinomialOrMatrix beta n Choose m EndBinomialOrMatrix"> <mml:semantics> <mml:mrow> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-OPEN"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> </mml:mstyle> <mml:mfrac linethickness="0"> <mml:mrow> <mml:mi> β </mml:mi> <mml:mi>n</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:mfrac> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-CLOSE"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:mstyle> </mml:mrow> <mml:annotation encoding="application/x-tex">\binom {\beta n}{m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sets of size <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that contain no <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -term arithmetic progression, provided that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m greater-than-or-slanted-equals upper C n Superscript 1 minus 1 slash left-parenthesis k minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo> ⩾ </mml:mo> <mml:mi>C</mml:mi> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">m \geqslant Cn^{1-1/(k-1)}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C"> <mml:semantics> <mml:mi>C</mml:mi> <mml:annotation encoding="application/x-tex">C</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a constant depending only on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="beta"> <mml:semantics> <mml:mi> β </mml:mi> <mml:annotation encoding="application/x-tex">\beta</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We also obtain new results, such as a sparse version of the Erdős–Frankl–Rödl Theorem on the number of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -free graphs and, as a consequence of the KŁR conjecture, we extend a result of Rödl and Ruciński on Ramsey properties in sparse random graphs to the general, non-symmetric setting.

The authors' abstract, as published at the source. Journal of the American Mathematical Society, 2014 · DOI ↗