×
Schacht, Mathias

Extremal results for random discrete structures. (English) Zbl 1351.05207

Ann. Math. (2) 184, No. 2, 333-365 (2016).
Summary: We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemerédi’s theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions, and we determine the threshold for Turán-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Y. Kohayakawa et al. [Acta Arith. 75, No. 2, 133–163 (1996; Zbl 0858.11009); Combinatorica 17, No. 2, 173–213 (1997; Zbl 0889.05068)] for Turán-type problems in random graphs. Similar results were obtained independently by D. Conlon and W. T. Gowers [Ann. Math. (2) 184, No. 2, 367–454 (2016; Zbl 1351.05204)].

Cited in 3 Reviews
Cited in 56 Documents

MSC:

05C80 Random graphs (graph-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C35 Extremal problems in graph theory
60C05 Combinatorial probability

Keywords:

random graphs; Szemerédi’s theorem; thresholds; Turán’s theorem

Citations:

Zbl 0858.11009; Zbl 0889.05068; Zbl 1351.05204
PDF BibTeX XML Cite
\textit{M. Schacht}, Ann. Math. (2) 184, No. 2, 333--365 (2016; Zbl 1351.05207)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] L. Babai, M. Simonovits, and J. Spencer, ”Extremal subgraphs of random graphs,” J. Graph Theory, vol. 14, iss. 5, pp. 599-622, 1990. · Zbl 0738.05048
[2] B. Bollobás, Extremal Graph Theory, New York: Academic Press [Harcourt Brace Jovanovich, Publishers], 1978, vol. 11. · Zbl 0419.05031
[3] B. Bollobás, Modern Graph Theory, New York: Springer-Verlag, 1998, vol. 184. · Zbl 0902.05016
[4] B. Bollobás, Random Graphs, Second ed., Cambridge: Cambridge Univ. Press, 2001, vol. 73. · Zbl 0979.05003
[5] J. A. Bondy and U. S. R. Murty, Graph Theory, New York: Springer-Verlag, 2008, vol. 244. · Zbl 1134.05001
[6] D. Conlon and W. T. Gowers, ”Combinatorial theorems in sparse random sets,” Ann. of Math., vol. 184, pp. 367-454, 2016. · Zbl 1351.05204
[7] R. Diestel, Graph Theory, Fourth ed., New York: Springer-Verlag, 2010, vol. 173. · Zbl 1204.05001
[8] P. Erdös and A. H. Stone, ”On the structure of linear graphs,” Bull. Amer. Math. Soc., vol. 52, pp. 1087-1091, 1946. · Zbl 0063.01277
[9] P. ErdHos, ”On sequences of integers no one of which divides the product of two others and on some related problems,” Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk, vol. 2, pp. 74-82, 1938. · Zbl 0020.00504
[10] P. ErdHos, ”On extremal problems of graphs and generalized graphs,” Israel J. Math., vol. 2, pp. 183-190, 1964. · Zbl 0129.39905
[11] P. ErdHos and M. Simonovits, ”A limit theorem in graph theory,” Studia Sci. Math. Hungar, vol. 1, pp. 51-57, 1966. · Zbl 0129.39905
[12] P. ErdHos and M. Simonovits, ”Supersaturated graphs and hypergraphs,” Combinatorica, vol. 3, iss. 2, pp. 181-192, 1983. · Zbl 0529.05027
[13] P. Erdös and P. Turán, ”On some sequences of integers,” J. London Math. Soc., vol. S1-11, iss. 4, pp. 261-264, 1936. · Zbl 0015.15203
[14] P. Frankl, R. L. Graham, and V. Rödl, ”Quantitative theorems for regular systems of equations,” J. Combin. Theory Ser. A, vol. 47, iss. 2, pp. 246-261, 1988. · Zbl 0654.05002
[15] P. Frankl and V. Rödl, ”Large triangle-free subgraphs in graphs without \(K_4\),” Graphs Combin., vol. 2, iss. 2, pp. 135-144, 1986. · Zbl 0596.05037
[16] E. Friedgut, V. Rödl, and M. Schacht, ”Ramsey properties of random discrete structures,” Random Structures Algorithms, vol. 37, iss. 4, pp. 407-436, 2010. · Zbl 1228.05284
[17] Z. F-redi, ”Random Ramsey graphs for the four-cycle,” Discrete Math., vol. 126, iss. 1-3, pp. 407-410, 1994. · Zbl 0792.05128
[18] H. Furstenberg and Y. Katznelson, ”An ergodic Szemerédi theorem for commuting transformations,” J. Analyse Math., vol. 34, pp. 275-291 (1979), 1978. · Zbl 0426.28014
[19] S. Gerke, Random graphs with constraints, 2005.
[20] S. Gerke, T. Schickinger, and A. Steger, ”\(K_5\)-free subgraphs of random graphs,” Random Structures Algorithms, vol. 24, iss. 2, pp. 194-232, 2004. · Zbl 1035.05084
[21] R. Graham, V. Rödl, and A. Ruciński, ”On Schur properties of random subsets of integers,” J. Number Theory, vol. 61, iss. 2, pp. 388-408, 1996. · Zbl 0880.05081
[22] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, Hoboken, NJ: John Wiley & Sons, 2013. · Zbl 1280.05001
[23] P. E. Haxell, Y. Kohayakawa, and T. Łuczak, ”Turán’s extremal problem in random graphs: forbidding even cycles,” J. Combin. Theory Ser. B, vol. 64, iss. 2, pp. 273-287, 1995. · Zbl 0828.05056
[24] P. E. Haxell, Y. Kohayakawa, and T. Łuczak, ”Turán’s extremal problem in random graphs: forbidding odd cycles,” Combinatorica, vol. 16, iss. 1, pp. 107-122, 1996. · Zbl 0853.05072
[25] S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, New York: Wiley-Interscience, 2000. · Zbl 0968.05003
[26] G. Katona, T. Nemetz, and M. Simonovits, ”On a problem of Turán in the theory of graphs,” Mat. Lapok, vol. 15, pp. 228-238, 1964. · Zbl 0138.19402
[27] Y. Kohayakawa, B. Kreuter, and A. Steger, ”An extremal problem for random graphs and the number of graphs with large even-girth,” Combinatorica, vol. 18, iss. 1, pp. 101-120, 1998. · Zbl 0910.05059
[28] Y. Kohayakawa, T. Łuczak, and V. Rödl, ”Arithmetic progressions of length three in subsets of a random set,” Acta Arith., vol. 75, iss. 2, pp. 133-163, 1996. · Zbl 0858.11009
[29] Y. Kohayakawa, T. Łuczak, and V. Rödl, ”On \(K^4\)-free subgraphs of random graphs,” Combinatorica, vol. 17, iss. 2, pp. 173-213, 1997. · Zbl 0889.05068
[30] Y. Kohayakawa, V. Rödl, and M. Schacht, ”The Turán theorem for random graphs,” Combin. Probab. Comput., vol. 13, iss. 1, pp. 61-91, 2004. · Zbl 1048.05075
[31] T. Kövari, V. T. Sós, and P. Turán, ”On a problem of K. Zarankiewicz,” Colloquium Math., vol. 3, pp. 50-57, 1954. · Zbl 0055.00704
[32] B. Kreuter, Probabilistic versions of Ramsey’s and Turán’s theorems, 1997.
[33] W. Mantel, ”Vraagstuk xxviii,” Wiskundige Opgaven, vol. 10, pp. 60-61, 1907. · JFM 38.0270.01
[34] R. Rado, ”Studien zur Kombinatorik,” Math. Z., vol. 36, iss. 1, pp. 424-470, 1933. · Zbl 0006.14603
[35] V. Rödl and A. Ruciński, ”Threshold functions for Ramsey properties,” J. Amer. Math. Soc., vol. 8, iss. 4, pp. 917-942, 1995. · Zbl 0846.05079
[36] V. Rödl and A. Ruciński, ”Rado partition theorem for random subsets of integers,” Proc. London Math. Soc., vol. 74, iss. 3, pp. 481-502, 1997. · Zbl 0880.05080
[37] V. Rödl, A. Ruciński, and M. Schacht, ”Ramsey properties of random \(k\)-partite, \(k\)-uniform hypergraphs,” SIAM J. Discrete Math., vol. 21, iss. 2, pp. 442-460, 2007. · Zbl 1140.05043
[38] I. Schur, ”Über die Kongruenz \(x^m+y^m\equiv z^m (\text{mod} p)\),” Jahresber. Deutsch. Math.-Verein., vol. 25, pp. 114-117, 1916. · JFM 46.0193.02
[39] T. Szabó and V. H. Vu, ”Turán’s theorem in sparse random graphs,” Random Structures Algorithms, vol. 23, iss. 3, pp. 225-234, 2003. · Zbl 1028.05101
[40] E. Szemerédi, ”On sets of integers containing no \(k\) elements in arithmetic progression,” Acta Arith., vol. 27, pp. 199-245, 1975. · Zbl 0303.10056
[41] P. Turán, ”Eine Extremalaufgabe aus der Graphentheorie,” Mat. Fiz. Lapok, vol. 48, pp. 436-452, 1941. · Zbl 0026.26903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.