Combinatorial theorems in sparse random sets. (English) Zbl 1351.05204

Conlon, D.; Gowers, W. T.

Ann. Math. (2) 184, No. 2, 367-454 (2016).

Summary: We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Turán’s theorem, Szemerédi’s theorem and Ramsey’s theorem, hold almost surely inside sparse random sets. For instance, we extend Turán’s theorem to the random setting by showing that for every \(\epsilon > 0\) and every positive integer \(t \geq 3\) there exists a constant \(C\) such that, if \(G\) is a random graph on \(n\) vertices where each edge is chosen independently with probability at least \(C n^{-2/(t+1)}\), then, with probability tending to 1 as \(n\) tends to infinity, every subgraph of \(G\) with at least \(\left(1 - \frac{1}{t-1} + \epsilon\right) e(G)\) edges contains a copy of \(K_t\). This is sharp up to the constant \(C\). We also show how to prove sparse analogues of structural results, giving two main applications, a stability version of the random Turán theorem stated above and a sparse hypergraph removal lemma. Many similar results have recently been obtained independently in a different way by M. Schacht [Ann. Math. (2) 184, No. 2, 333–365 (2016; Zbl 1351.05207)] and by E. Friedgut et al. [Random Struct. Algorithms 37, No. 4, 407–436 (2010; Zbl 1228.05284)].

MSC:

05C80	Random graphs (graph-theoretic aspects)
05D40	Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C42	Density (toughness, etc.)
05D10	Ramsey theory

Keywords:

extremal combinatorics; random graphs; random sets; sparse analogues

Citations:

Zbl 1228.05284; Zbl 1351.05207

References:

[1]	J. Balogh, R. Morris, and W. Samotij, ”Independent sets in hypergraphs,” J. Amer. Math. Soc., vol. 28, iss. 3, pp. 669-709, 2015. · Zbl 1310.05154
[2]	V. Bergelson and A. Leibman, ”Polynomial extensions of van der Waerden’s and Szemerédi’s theorems,” J. Amer. Math. Soc., vol. 9, iss. 3, pp. 725-753, 1996. · Zbl 0870.11015
[3]	B. Bollobás, Extremal Graph Theory, Mineola, NY: Dover Publications, 2004. · Zbl 1099.05044
[4]	D. De Caen and Z. Füredi, ”The maximum size of 3-uniform hypergraphs not containing a Fano plane,” J. Combin. Theory Ser. B, vol. 78, iss. 2, pp. 274-276, 2000. · Zbl 1027.05073
[5]	D. Conlon, ”Combinatorial theorems relative to a random set,” in Proceedings of the International Congress of Mathematicians 2014, Vol. 4, , pp. 303-328. · Zbl 1373.05175
[6]	D. Conlon, W. T. Gowers, W. Samotij, and M. Schacht, ”On the KŁR conjecture in random graphs,” Israel J. Math., vol. 203, iss. 1, pp. 535-580, 2014. · Zbl 1303.05175
[7]	P. ErdHos, ”On the number of complete subgraphs contained in certain graphs,” Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 7, pp. 459-464, 1962. · Zbl 0116.01202
[8]	P. ErdHos and M. Simonovits, ”Supersaturated graphs and hypergraphs,” Combinatorica, vol. 3, iss. 2, pp. 181-192, 1983. · Zbl 0529.05027
[9]	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
[10]	E. Friedgut, ”Sharp thresholds of graph properties, and the \(k\)-SAT problem,” J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999. · Zbl 0932.05084
[11]	E. Friedgut, V. Rödl, A. Ruciński, and P. Tetali, ”A sharp threshold for random graphs with a monochromatic triangle in every edge coloring,” Mem. Amer. Math. Soc., vol. 179, iss. 845, p. vi, 2006. · Zbl 1087.05052
[12]	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
[13]	Z. Füredi, ”Random Ramsey graphs for the four-cycle,” Discrete Math., vol. 126, iss. 1-3, pp. 407-410, 1994. · Zbl 0792.05128
[14]	Z. Füredi and M. Simonovits, ”Triple systems not containing a Fano configuration,” Combin. Probab. Comput., vol. 14, iss. 4, pp. 467-484, 2005. · Zbl 1075.05062
[15]	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
[16]	S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, ”Small subsets inherit sparse \(\epsilon\)-regularity,” J. Combin. Theory Ser. B, vol. 97, iss. 1, pp. 34-56, 2007. · Zbl 1111.05090
[17]	S. Gerke, H. J. Prömel, T. Schickinger, A. Steger, and A. Taraz, ”\(K_4\)-free subgraphs of random graphs revisited,” Combinatorica, vol. 27, iss. 3, pp. 329-365, 2007. · Zbl 1136.05067
[18]	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
[19]	W. T. Gowers, ”A new proof of Szemerédi’s theorem,” Geom. Funct. Anal., vol. 11, iss. 3, pp. 465-588, 2001. · Zbl 1028.11005
[20]	W. T. Gowers, ”Quasirandomness, counting and regularity for 3-uniform hypergraphs,” Combin. Probab. Comput., vol. 15, iss. 1-2, pp. 143-184, 2006. · Zbl 1082.05081
[21]	W. T. Gowers, ”Hypergraph regularity and the multidimensional Szemerédi theorem,” Ann. of Math., vol. 166, iss. 3, pp. 897-946, 2007. · Zbl 1159.05052
[22]	W. T. Gowers, ”Decompositions, approximate structure, transference, and the Hahn-Banach theorem,” Bull. Lond. Math. Soc., vol. 42, iss. 4, pp. 573-606, 2010. · Zbl 1233.05198
[23]	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
[24]	B. Green and T. Tao, ”The primes contain arbitrarily long arithmetic progressions,” Ann. of Math., vol. 167, iss. 2, pp. 481-547, 2008. · Zbl 1191.11025
[25]	M. Hamel and I. Łaba, ”Arithmetic structures in random sets,” Integers, vol. 8, p. 04, 2008. · Zbl 1195.11037
[26]	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
[27]	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
[28]	S. Janson, ”Poisson approximation for large deviations,” Random Structures Algorithms, vol. 1, iss. 2, pp. 221-229, 1990. · Zbl 0747.05079
[29]	S. Janson, K. Oleszkiewicz, and A. Ruciński, ”Upper tails for subgraph counts in random graphs,” Israel J. Math., vol. 142, pp. 61-92, 2004. · Zbl 1055.05136
[30]	S. Janson and A. Ruciński, ”The infamous upper tail,” Random Structures Algorithms, vol. 20, iss. 3, pp. 317-342, 2002. · Zbl 0996.60023
[31]	S. Janson and A. Ruciński, ”The deletion method for upper tail estimates,” Combinatorica, vol. 24, iss. 4, pp. 615-640, 2004. · Zbl 1074.60006
[32]	S. Janson and A. Ruciński, ”Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs,” Ark. Mat., vol. 49, iss. 1, pp. 79-96, 2011. · Zbl 1223.05201
[33]	P. Keevash and B. Sudakov, ”The Turán number of the Fano plane,” Combinatorica, vol. 25, iss. 5, pp. 561-574, 2005. · Zbl 1089.05074
[34]	Y. Kohayakawa, ”Szemerédi’s regularity lemma for sparse graphs,” in Foundations of Computational Mathematics, New York: Springer-Verlag, 1997, pp. 216-230. · Zbl 0868.05042
[35]	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
[36]	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
[37]	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
[38]	T. Łuczak, ”Randomness and regularity,” in International Congress of Mathematicians. Vol. III, Eur. Math. Soc., 2006, pp. 899-909. · Zbl 1099.05073
[39]	T. Łuczak, A. Ruciński, and B. Voigt, ”Ramsey properties of random graphs,” J. Combin. Theory Ser. B, vol. 56, iss. 1, pp. 55-68, 1992. · Zbl 0711.05041
[40]	B. Nagle, V. Rödl, and M. Schacht, ”The counting lemma for regular \(k\)-uniform hypergraphs,” Random Structures Algorithms, vol. 28, iss. 2, pp. 113-179, 2006. · Zbl 1093.05045
[41]	H. H. Nguyen, ”On two-point configurations in a random set,” Integers, vol. 9, p. a3, 41-45, 2009. · Zbl 1207.11021
[42]	R. Rado, ”Note on combinatorial analysis,” Proc. London Math. Soc., vol. 48, pp. 122-160, 1943. · Zbl 0028.33801
[43]	F. P. Ramsey, ”On a problem of formal logic,” Proc. London Math. Soc., vol. S2-30, iss. 1, p. 264, 1929. · JFM 55.0032.04
[44]	O. Reingold, L. Trevisan, M. Tulsiani, and S. Vadhan, ”Dense subsets of pseudorandom sets,” in Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, Washington DC: IEEE Computer Society, 2008, pp. 76-85.
[45]	V. Rödl and A. Ruciński, ”Lower bounds on probability thresholds for Ramsey properties,” in Combinatorics, Paul Erd\Hos is Eighty, Budapest: János Bolyai Math. Soc., 1993, vol. 1, pp. 317-346. · Zbl 0790.05078
[46]	V. Rödl and A. Ruciński, ”Random graphs with monochromatic triangles in every edge coloring,” Random Structures Algorithms, vol. 5, iss. 2, pp. 253-270, 1994. · Zbl 0790.05079
[47]	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
[48]	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
[49]	V. Rödl and A. Ruciński, ”Ramsey properties of random hypergraphs,” J. Combin. Theory Ser. A, vol. 81, iss. 1, pp. 1-33, 1998. · Zbl 0893.05011
[50]	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
[51]	V. Rödl and J. Skokan, ”Regularity lemma for \(k\)-uniform hypergraphs,” Random Structures Algorithms, vol. 25, iss. 1, pp. 1-42, 2004. · Zbl 1046.05042
[52]	K. F. Roth, ”On certain sets of integers,” J. London Math. Soc., vol. 28, pp. 104-109, 1953. · Zbl 0050.04002
[53]	W. Samotij, ”Stability results for random discrete structures,” Random Structures Algorithms, vol. 44, iss. 3, pp. 269-289, 2014. · Zbl 1290.05131
[54]	D. Saxton and A. Thomason, ”Hypergraph containers,” Invent. Math., vol. 201, iss. 3, pp. 925-992, 2015. · Zbl 1320.05085
[55]	M. Schacht, ”Extremal results for discrete random structures,” Ann. of Math., vol. 184, pp. 333-365, 2016. · Zbl 1351.05207
[56]	I. Schur, ”Über die Kongruenz \(x^m + y^m = z^m \, (\mbox{mod } p)\),” Jber. Deutsch. Mat. Verein., vol. 25, pp. 114-117, 1916. · JFM 46.0193.02
[57]	M. Simonovits, ”A method for solving extremal problems in graph theory, stability problems,” in Theory of Graphs, New York: Academic Press, 1968, pp. 279-319. · Zbl 0164.24604
[58]	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
[59]	E. Szemerédi, ”On sets of integers containing no \(k\) elements in arithmetic progression,” Acta Arith., vol. 27, pp. 199-245, 1975. · Zbl 0335.10054
[60]	E. Szemerédi, ”Regular partitions of graphs,” in Problèmes Combinatoires et Théorie des Graphes, Paris: CNRS, 1978, vol. 260, pp. 399-401. · Zbl 0413.05055
[61]	T. Tao, ”A variant of the hypergraph removal lemma,” J. Combin. Theory Ser. A, vol. 113, iss. 7, pp. 1257-1280, 2006. · Zbl 1105.05052
[62]	P. Turán, ”Eine Extremalaufgabe aus der Graphentheorie,” Mat. Fiz. Lapok, vol. 48, pp. 436-452, 1941. · Zbl 0026.26903
[63]	B. L. van der Waerden, ”Beweis einer Baudetschen Vermutung,” Nieuw. Arch. Wisk., vol. 15, pp. 212-216, 1927. · JFM 53.0073.12
[64]	P. Varnavides, ”On certain sets of positive density,” J. London Math. Soc., vol. 34, pp. 358-360, 1959. · Zbl 0088.25702
[65]	V. H. Vu, ”A large deviation result on the number of small subgraphs of a random graph,” Combin. Probab. Comput., vol. 10, iss. 1, pp. 79-94, 2001. · Zbl 0982.05092