Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

Request Permissions   Purchase Content 
 
 

 

Independent sets in hypergraphs


Authors: József Balogh, Robert Morris and Wojciech Samotij
Journal: J. Amer. Math. Soc. 28 (2015), 669-709
MSC (2010): Primary 05D40; Secondary 05C30, 05C35, 05C65
DOI: https://doi.org/10.1090/S0894-0347-2014-00816-X
Published electronically: August 7, 2014
MathSciNet review: 3327533
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \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 \ge 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.


References [Enhancements On Off] (What's this?)

  • [1] Alon N., Balogh J., Morris R., and Samotij W., Counting sum-free sets in Abelian groups, Israel J. Math., 199 (2014), 309-344.., https://doi.org/10.1007/s11856-013-0067-y
  • [2] Alon N., Balogh J., Morris R., and Samotij W., A refinement of the Cameron-Erdős conjecture, Proc. Lond. Math. Soc. (3) 108 (2014), no. 1, 44-72. MR 3162820, https://doi.org/10.1112/plms/pdt033
  • [3] Alon N. and Spencer J. H., The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651 (2009j:60004)
  • [4] Babai L., Simonovits M., and Spencer J., Extremal subgraphs of random graphs, J. Graph Theory 14 (1990), no. 5, 599-622. MR 1073101 (91h:05112), https://doi.org/10.1002/jgt.3190140511
  • [5] Balogh J., Bollobás B., and Simonovits M., The number of graphs without forbidden subgraphs, J. Combin. Theory Ser. B 91 (2004), no. 1, 1-24. MR 2047528 (2005b:05122), https://doi.org/10.1016/j.jctb.2003.08.001
  • [6] Balogh J., Bollobás B., and Simonovits M., The typical structure of graphs without given excluded subgraphs, Random Struct. Algorithms 34 (2009), no. 3, 305-318. MR 2504400 (2010e:05270), https://doi.org/10.1002/rsa.20242
  • [7] Balogh J., Morris R., Samotij W., and Warnke L., The typical structure of sparse $ K_{r+1}$-free graphs. submitted.
  • [8] Balogh J. and Mubayi D., Almost all triple systems with independent neighborhoods are semi-bipartite, J. Combin. Theory Ser. A 118 (2011), no. 4, 1494-1518. MR 2771596 (2012e:05261), https://doi.org/10.1016/j.jcta.2011.01.006
  • [9] Balogh J. and Mubayi D., Almost all triangle-free triple systems are tripartite, Combinatorica 32 (2012), no. 2, 143-169. MR 2927636, https://doi.org/10.1007/s00493-012-2657-4
  • [10] Balogh J. and Samotij W., The number of $ K_{m,m}$-free graphs, Combinatorica 31 (2011), no. 2, 131-150. MR 2848247, https://doi.org/10.1007/s00493-011-2610-y
  • [11] Balogh J. and Samotij W., The number of $ K_{s,t}$-free graphs, J. Lond. Math. Soc. (2) 83 (2011), no. 2, 368-388. MR 2776642 (2012g:05103), https://doi.org/10.1112/jlms/jdq086
  • [12] Behrisch M., Random graphs without a short cycle (2002). Master's thesis, Humboldt-Universität zu Berlin.
  • [13] Bergelson V. and Leibman A., Polynomial extensions of van der Waerden's and Szemerédi's theorems, J. Amer. Math. Soc. 9 (1996), no. 3, 725-753. MR 1325795 (96j:11013), https://doi.org/10.1090/S0894-0347-96-00194-4
  • [14] Conlon D. and Gowers W.T., Combinatorial theorems in sparse random sets. submitted.
  • [15] Conlon D., Gowers W.T., Samotij W., and Schacht M., On the KŁR conjecture in random graphs. To appear in Israel J. Math.
  • [16] Erdős P., Some recent results on extremal problems in graph theory. Results, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 117-123 (English); pp. 124-130 (French). MR 0227049 (37 #2634)
  • [17] Erdős P., Frankl P., and Rödl V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), no. 2, 113-121. MR 932119 (89b:05102), https://doi.org/10.1007/BF01788085
  • [18] Erdős P., Kleitman D. J., and Rothschild B. L., Asymptotic enumeration of $ K_{n}$-free graphs, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Accad. Naz. Lincei, Rome, 1976, pp. 19-27. Atti dei Convegni Lincei, No. 17 (English, with Italian summary). MR 0463020 (57 #2984)
  • [19] Erdős P. and Simonovits M., Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), no. 2, 181-192. MR 726456 (85e:05125), https://doi.org/10.1007/BF02579292
  • [20] Erdős P. and Stone A. H., On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087-1091. MR 0018807 (8,333b)
  • [21] Fox J., A new proof of the graph removal lemma, Ann. Math. (2) 174 (2011), no. 1, 561-579. MR 2811609 (2012j:05224), https://doi.org/10.4007/annals.2011.174.1.17
  • [22] Frankl P. and Rödl V., Large triangle-free subgraphs in graphs without $ K_4$, Graphs Combin. 2 (1986), no. 2, 135-144. MR 932121 (89b:05124), https://doi.org/10.1007/BF01788087
  • [23] Friedgut E., Rödl V., and Schacht M., Ramsey properties of random discrete structures, Random Struct. Algorithms 37 (2010), no. 4, 407-436. MR 2760356 (2012a:05274), https://doi.org/10.1002/rsa.20352
  • [24] Füredi Z., Random Ramsey graphs for the four-cycle, Discrete Math. 126 (1994), no. 1-3, 407-410. MR 1264510 (94m:05131), https://doi.org/10.1016/0012-365X(94)90287-9
  • [25] Füredi Z., Pikhurko O., and Simonovits M., On triple systems with independent neighbourhoods, Combin. Probab. Comput. 14 (2005), no. 5-6, 795-813. MR 2174657 (2006g:05141), https://doi.org/10.1017/S0963548305006905
  • [26] Füredi Z. and Simonovits M., Triple systems not containing a Fano configuration, Combin. Probab. Comput. 14 (2005), no. 4, 467-484. MR 2160414 (2006d:05034), https://doi.org/10.1017/S0963548305006784
  • [27] Furstenberg H. and Katznelson Y., An ergodic Szemerédi theorem for commuting transformations, J. Analyse Math. 34 (1978), 275-291 (1979). MR 531279 (82c:28032), https://doi.org/10.1007/BF02790016
  • [28] Gerke S., Random graphs with constraints (2005).
  • [29] Gerke S., Kohayakawa Y., Rödl V., and Steger A., Small subsets inherit sparse $ \epsilon $-regularity, J. Combin. Theory Ser. B 97 (2007), no. 1, 34-56. MR 2278123 (2007i:05091), https://doi.org/10.1016/j.jctb.2006.03.004
  • [30] Gerke S., Prömel H. J., Schickinger T., Steger A., and Taraz A., $ K_4$-free subgraphs of random graphs revisited, Combinatorica 27 (2007), no. 3, 329-365. MR 2345813 (2009a:05192), https://doi.org/10.1007/s00493-007-2010-5
  • [31] Gerke S., Schickinger T., and Steger A., $ K_5$-free subgraphs of random graphs, Random Struct. Algorithms 24 (2004), no. 2, 194-232. MR 2035876 (2005b:05202), https://doi.org/10.1002/rsa.20000
  • [32] Gerke S. and Steger A., The sparse regularity lemma and its applications, Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge University Press, Cambridge, 2005, pp. 227-258. MR 2187740 (2006m:05118), https://doi.org/10.1017/CBO9780511734885.010
  • [33] Gowers W. T., Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. Math. (2) 166 (2007), no. 3, 897-946. MR 2373376 (2009d:05250), https://doi.org/10.4007/annals.2007.166.897
  • [34] Haxell P. E., Kohayakawa Y., and Łuczak T., Turán's extremal problem in random graphs: forbidding even cycles, J. Combin. Theory Ser. B 64 (1995), no. 2, 273-287. MR 1339852 (96e:05151), https://doi.org/10.1006/jctb.1995.1035
  • [35] Haxell P. E., Kohayakawa Y., and Łuczak T., Turán's extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), no. 1, 107-122. MR 1394514 (97k:05180), https://doi.org/10.1007/BF01300129
  • [36] Keevash P. and Mubayi D., Stability theorems for cancellative hypergraphs, J. Combin. Theory Ser. B 92 (2004), no. 1, 163-175. MR 2078500 (2005e:05101), https://doi.org/10.1016/j.jctb.2004.05.003
  • [37] Keevash P. and Sudakov B., The Turán number of the Fano plane, Combinatorica 25 (2005), no. 5, 561-574. MR 2176425 (2006f:05093), https://doi.org/10.1007/s00493-005-0034-2
  • [38] Kleitman D. J. and Winston K. J., On the number of graphs without $ 4$-cycles, Discrete Math. 41 (1982), no. 2, 167-172. MR 676877 (85a:05043), https://doi.org/10.1016/0012-365X(82)90204-7
  • [39] Kohayakawa Y., Szemerédi's regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997) Springer, Berlin, 1997, pp. 216-230. MR 1661982 (99g:05145)
  • [40] Kohayakawa Y. and Kreuter B., Threshold functions for asymmetric Ramsey properties involving cycles, Random Struct. Algorithms 11 (1997), no. 3, 245-276. MR 1609513 (99g:05159), https://doi.org/10.1002/(SICI)1098-2418(199710)11:3$ \langle $245::AID-RSA3$ \rangle $3.3.CO;2-I
  • [41] Kohayakawa Y., Łuczak T., and Rödl V., Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133-163. MR 1379396 (97b:11011)
  • [42] Kohayakawa Y., Łuczak T., and Rödl V., On $ K^4$-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173-213. MR 1479298 (98h:05166), https://doi.org/10.1007/BF01200906
  • [43] Kohayakawa Y. and Rödl V., Regular pairs in sparse random graphs. I, Random Struct. Algorithms 22 (2003), no. 4, 359-434. MR 1980964 (2004b:05187), https://doi.org/10.1002/rsa.10081
  • [44] Kohayakawa Y., Rödl V., and Schacht M., The Turán theorem for random graphs, Combin. Probab. Comput. 13 (2004), no. 1, 61-91. MR 2034303 (2004k:05180), https://doi.org/10.1017/S0963548303005856
  • [45] Kohayakawa Y., Schacht M., and Spöhel R., Upper bounds on probability thresholds for asymmetric Ramsey properties, Random Struct. Algorithms 44 (2014), no. 1, 1-28. MR 3143588, https://doi.org/10.1002/rsa.20446
  • [46] Łuczak T., On triangle-free random graphs, Random Struct. Algorithms 16 (2000), no. 3, 260-276. MR 1749289 (2000m:05212), https://doi.org/10.1002/(SICI)1098-2418(200005)16:3$ \langle $260::AID-RSA3$ \rangle $3.3.CO;2-H
  • [47] Marciniszyn M., Skokan J., Spöhel R., and Steger A., Asymmetric Ramsey properties of random graphs involving cliques, Random Struct. Algorithms 34 (2009), no. 4, 419-453. MR 2531778 (2010i:05313), https://doi.org/10.1002/rsa.20239
  • [48] Nagle B., Rödl V., and Schacht M., Extremal hypergraph problems and the regularity method, Topics in discrete mathematics, Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 247-278. MR 2249275 (2007d:05083), https://doi.org/10.1007/3-540-33700-8_16
  • [49] Osthus D., Prömel H., and Taraz A., For which densities are random triangle-free graphs almost surely bipartite?, Combinatorica 23 (2003), no. 1, 105-150. Paul Erdős and his mathematics (Budapest, 1999). MR 1996629 (2004e:05179), https://doi.org/10.1007/s00493-003-0016-1
  • [50] Person Y. and Schacht M., Almost all hypergraphs without Fano planes are bipartite, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 217-226. MR 2809321 (2012i:05192)
  • [51] Ramsey F. P., On a Problem of Formal Logic, Proc. London Math. Soc. S2-30, no. 1, 264. MR 1576401, https://doi.org/10.1112/plms/s2-30.1.264
  • [52] Rödl V. and 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. 1 (1993), 317-346.
  • [53] Rödl V. and Ruciński A., Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917-942. MR 1276825 (96h:05141), https://doi.org/10.2307/2152833
  • [54] Rödl V. and Skokan J., Applications of the regularity lemma for uniform hypergraphs, Random Struct. Algorithms 28 (2006), no. 2, 180-194. MR 2198496 (2006j:05099), https://doi.org/10.1002/rsa.20108
  • [55] Ruzsa I. Z. and Szemerédi E., Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939-945. MR 519318 (80c:05116)
  • [56] Samotij W., Stability results for random discrete structures. To appear in Random Struct. Algorithms.
  • [57] Saxton D. and Thomason A., Hypergraph containers. submitted.
  • [58] Schacht M., Extremal results for random discrete structures. submitted.
  • [59] Scott A., Szemerédi's regularity lemma for matrices and sparse graphs, Combin. Probab. Comput. 20 (2011), no. 3, 455-466. MR 2784637 (2012e:05316), https://doi.org/10.1017/S0963548310000490
  • [60] Simonovits M., A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 279-319. MR 0233735 (38 #2056)
  • [61] Szabó T. and Vu V. H., Turán's theorem in sparse random graphs, Random Struct. Algorithms 23 (2003), no. 3, 225-234. MR 1999036 (2004f:05167), https://doi.org/10.1002/rsa.10088
  • [62] Szemerédi E., On sets of integers containing no $ k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199-245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312 (51 #5547)
  • [63] Szemerédi E., Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399-401 (English, with French summary). MR 540024 (81i:05095)
  • [64] Turán P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436-452 (Hungarian, with German summary). MR 0018405 (8,284j)
  • [65] Varnavides P., On certain sets of positive density, J. London Math. Soc. 34 (1959), 358-360. MR 0106865 (21 #5595)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 05D40, 05C30, 05C35, 05C65

Retrieve articles in all journals with MSC (2010): 05D40, 05C30, 05C35, 05C65


Additional Information

József Balogh
Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801
Email: jobal@math.uiuc.edu

Robert Morris
Affiliation: IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil
Email: rob@impa.br

Wojciech Samotij
Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Trinity College, Cambridge CB2 1TQ, UK
Email: ws299@cam.ac.uk

DOI: https://doi.org/10.1090/S0894-0347-2014-00816-X
Received by editor(s): June 16, 2012
Received by editor(s) in revised form: March 21, 2014
Published electronically: August 7, 2014
Additional Notes: The first author was supported in part by NSF Career Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099.
The second author was supported in part by CNPq bolsa de Produtivdade em Pesquisa.
The third author was supported in part by ERC Advanced Grant DMMCA and a Trinity College JRF
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society