Independent sets in hypergraphs

Balogh, József¹ ; Morris, Robert² ; Samotij, Wojciech³

¹ Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801
² IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil
³ School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Trinity College, Cambridge CB2 1TQ, UK

Journal of the American Mathematical Society, Tome 28 (2015) no. 3, pp. 669-709

Résumé

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 $\beta$ and integer $k$, there are at most $\binom {\beta n}{m}$ sets of size $m$ that contain no $k$-term arithmetic progression, provided that $m \geqslant Cn^{1-1/(k-1)}$, where $C$ is a constant depending only on $\beta$ and $k$. We also obtain new results, such as a sparse version of the Erdős–Frankl–Rödl Theorem on the number of $H$-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.

Détail

DOI : 10.1090/S0894-0347-2014-00816-X

Bibliographie

[1] Alon N., Balogh J., Morris R., Samotij W. Counting sum-free sets in Abelian groups Israel J. Math., 2014

[2] Alon, Noga, Balogh, Jã³Zsef, Morris, Robert, Samotij, Wojciech A refinement of the Cameron-Erdős conjecture Proc. Lond. Math. Soc. (3) 2014 44 72

[3] Alon, Noga, Spencer, Joel H. The probabilistic method 2008

[4] Babai, Lã¡Szlã³, Simonovits, Miklã³S, Spencer, Joel Extremal subgraphs of random graphs J. Graph Theory 1990 599 622

[5] Balogh, Jã³Zsef, Bollobã¡S, Bã©La, Simonovits, Miklã³S The number of graphs without forbidden subgraphs J. Combin. Theory Ser. B 2004 1 24

[6] Balogh, Jã³Zsef, Bollobã¡S, Bã©La, Simonovits, Miklã³S The typical structure of graphs without given excluded subgraphs Random Structures Algorithms 2009 305 318

[7] Balogh J., Morris R., Samotij W., Warnke L. The typical structure of sparse 𝐾ᵣ₊₁-free graphs

[8] Balogh, Jã³Zsef, Mubayi, Dhruv Almost all triple systems with independent neighborhoods are semi-bipartite J. Combin. Theory Ser. A 2011 1494 1518

[9] Balogh, Jã³Zsef, Mubayi, Dhruv Almost all triangle-free triple systems are tripartite Combinatorica 2012 143 169

[10] Balogh, Jã³Zsef, Samotij, Wojciech The number of 𝐾_{𝑚,𝑚}-free graphs Combinatorica 2011 131 150

[11] Balogh, Jã³Zsef, Samotij, Wojciech The number of 𝐾_{𝑠,𝑡}-free graphs J. Lond. Math. Soc. (2) 2011 368 388

[12] Behrisch M. Random graphs without a short cycle 2002

[13] Bergelson, V., Leibman, A. Polynomial extensions of van der Waerden’s and Szemerédi’s theorems J. Amer. Math. Soc. 1996 725 753

[14] Conlon D., Gowers W.T. Combinatorial theorems in sparse random sets

[15] Conlon D., Gowers W.T., Samotij W., Schacht M. On the KŁR conjecture in random graphs

[16] Erdå‘S, P. Some recent results on extremal problems in graph theory. Results 1967

[17] Erdå‘S, P., Frankl, P., Rã¶Dl, V. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent Graphs Combin. 1986 113 121

[18] Erdå‘S, P., Kleitman, D. J., Rothschild, B. L. Asymptotic enumeration of 𝐾_{𝑛}-free graphs 1976 19 27

[19] Erdå‘S, Paul, Simonovits, Miklã³S Supersaturated graphs and hypergraphs Combinatorica 1983 181 192

[20] Erdã¶S, P., Stone, A. H. On the structure of linear graphs Bull. Amer. Math. Soc. 1946 1087 1091

[21] Fox, Jacob A new proof of the graph removal lemma Ann. of Math. (2) 2011 561 579

[22] Frankl, P., Rã¶Dl, V. Large triangle-free subgraphs in graphs without 𝐾₄ Graphs Combin. 1986 135 144

[23] Friedgut, Ehud, Rã¶Dl, Vojtä›Ch, Schacht, Mathias Ramsey properties of random discrete structures Random Structures Algorithms 2010 407 436

[24] Fã¼Redi, Zoltã¡N Random Ramsey graphs for the four-cycle Discrete Math. 1994 407 410

[25] Fã¼Redi, Zoltã¡N, Pikhurko, Oleg, Simonovits, Miklã³S On triple systems with independent neighbourhoods Combin. Probab. Comput. 2005 795 813

[26] Fã¼Redi, Zoltã¡N, Simonovits, Miklã³S Triple systems not containing a Fano configuration Combin. Probab. Comput. 2005 467 484

[27] Furstenberg, H., Katznelson, Y. An ergodic Szemerédi theorem for commuting transformations J. Analyse Math. 1978

[28] Gerke S. Random graphs with constraints 2005

[29] Gerke, Stefanie, Kohayakawa, Yoshiharu, Rã¶Dl, Vojtä›Ch, Steger, Angelika Small subsets inherit sparse 𝜀-regularity J. Combin. Theory Ser. B 2007 34 56

[30] Gerke, S., Prã¶Mel, H. J., Schickinger, T., Steger, A., Taraz, A. 𝐾₄-free subgraphs of random graphs revisited Combinatorica 2007 329 365

[31] Gerke, S., Schickinger, T., Steger, A. 𝐾₅-free subgraphs of random graphs Random Structures Algorithms 2004 194 232

[32] Gerke, Stefanie, Steger, Angelika The sparse regularity lemma and its applications 2005 227 258

[33] Gowers, W. T. Hypergraph regularity and the multidimensional Szemerédi theorem Ann. of Math. (2) 2007 897 946

[34] Haxell, P. E., Kohayakawa, Y., ŁUczak, T. Turán’s extremal problem in random graphs: forbidding even cycles J. Combin. Theory Ser. B 1995 273 287

[35] Haxell, P. E., Kohayakawa, Y., ŁUczak, T. Turán’s extremal problem in random graphs: forbidding odd cycles Combinatorica 1996 107 122

[36] Keevash, Peter, Mubayi, Dhruv Stability theorems for cancellative hypergraphs J. Combin. Theory Ser. B 2004 163 175

[37] Keevash, Peter, Sudakov, Benny The Turán number of the Fano plane Combinatorica 2005 561 574

[38] Kleitman, Daniel J., Winston, Kenneth J. On the number of graphs without 4-cycles Discrete Math. 1982 167 172

[39] Kohayakawa, Y. Szemerédi’s regularity lemma for sparse graphs 1997 216 230

[40] Kohayakawa, Y., Kreuter, B. Threshold functions for asymmetric Ramsey properties involving cycles Random Structures Algorithms 1997 245 276

[41] Kohayakawa, Yoshiharu, ŁUczak, Tomasz, Rã¶Dl, Vojtä›Ch Arithmetic progressions of length three in subsets of a random set Acta Arith. 1996 133 163

[42] Kohayakawa, Y., ŁUczak, T., Rã¶Dl, V. On 𝐾⁴-free subgraphs of random graphs Combinatorica 1997 173 213

[43] Kohayakawa, Y., Rã¶Dl, V. Regular pairs in sparse random graphs. I Random Structures Algorithms 2003 359 434

[44] Kohayakawa, Yoshiharu, Rã¶Dl, Vojtä›Ch, Schacht, Mathias The Turán theorem for random graphs Combin. Probab. Comput. 2004 61 91

[45] Kohayakawa, Yoshiharu, Schacht, Mathias, Spã¶Hel, Reto Upper bounds on probability thresholds for asymmetric Ramsey properties Random Structures Algorithms 2014 1 28

[46] ŁUczak, Tomasz On triangle-free random graphs Random Structures Algorithms 2000 260 276

[47] Marciniszyn, Martin, Skokan, Jozef, Spã¶Hel, Reto, Steger, Angelika Asymmetric Ramsey properties of random graphs involving cliques Random Structures Algorithms 2009 419 453

[48] Nagle, Brendan, Rã¶Dl, Vojtä›Ch, Schacht, Mathias Extremal hypergraph problems and the regularity method 2006 247 278

[49] Osthus, Deryk, Prã¶Mel, Hans Jã¼Rgen, Taraz, Anusch For which densities are random triangle-free graphs almost surely bipartite? Combinatorica 2003 105 150

[50] Person, Yury, Schacht, Mathias Almost all hypergraphs without Fano planes are bipartite 2009 217 226

[51] Ramsey, F. P. On a Problem of Formal Logic Proc. London Math. Soc. (2) 1929 264 286

[52] Rã¶Dl V., Ruciå„Ski A. Lower bounds on probability thresholds for Ramsey properties, Combinatorics, Paul Erdős is Eighty Bolyai Soc. Math. Stud., János Bolyai Math. Soc. 1993 317 346

[53] Rã¶Dl, Vojtä›Ch, Ruciå„Ski, Andrzej Threshold functions for Ramsey properties J. Amer. Math. Soc. 1995 917 942

[54] Rã¶Dl, Vojtä›Ch, Skokan, Jozef Applications of the regularity lemma for uniform hypergraphs Random Structures Algorithms 2006 180 194

[55] Ruzsa, I. Z., Szemerã©Di, E. Triple systems with no six points carrying three triangles 1978 939 945

[56] Samotij W. Stability results for random discrete structures

[57] Saxton D., Thomason A. Hypergraph containers

[58] Schacht M. Extremal results for random discrete structures

[59] Scott, Alexander Szemerédi’s regularity lemma for matrices and sparse graphs Combin. Probab. Comput. 2011 455 466

[60] Simonovits, M. A method for solving extremal problems in graph theory, stability problems 1968 279 319

[61] Szabã³, Tibor, Vu, Van H. Turán’s theorem in sparse random graphs Random Structures Algorithms 2003 225 234

[62] Szemerã©Di, E. On sets of integers containing no 𝑘 elements in arithmetic progression Acta Arith. 1975 199 245

[63] Szemerã©Di, Endre Regular partitions of graphs 1978 399 401

[64] Turã¡N, Paul Eine Extremalaufgabe aus der Graphentheorie Mat. Fiz. Lapok 1941 436 452

[65] Varnavides, P. On certain sets of positive density J. London Math. Soc. 1959 358 360