Proof of a conjecture on induced subgraphs of Ramsey graphs

Kwan, Matthew; Sudakov, Benny

doi:10.1090/tran/7729

Proof of a conjecture on induced subgraphs of Ramsey graphs
HTML articles powered by AMS MathViewer

by Matthew Kwan and Benny Sudakov PDF

Trans. Amer. Math. Soc. 372 (2019), 5571-5594 Request permission

Abstract:

An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log n$. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research toward showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. More than 25 years ago, Erdős, Faudree, and Sós conjectured that in any $C$-Ramsey graph there are $\Omega (n^{5/2})$ induced subgraphs, no pair of which have the same numbers of vertices and edges. Improving on earlier results of Alon, Balogh, Kostochka, and Samotij, in this paper we prove this conjecture.

References

Noga Alon, József Balogh, Alexandr Kostochka, and Wojciech Samotij, Sizes of induced subgraphs of Ramsey graphs, Combin. Probab. Comput. 18 (2009), no. 4, 459–476. MR 2507733, DOI 10.1017/S0963548309009869
Noga Alon and Béla Bollobás, Graphs with a small number of distinct induced subgraphs, Discrete Math. 75 (1989), no. 1-3, 23–30. Graph theory and combinatorics (Cambridge, 1988). MR 1001382, DOI 10.1016/0012-365X(89)90074-5
N. Alon, D. Hefetz, M. Krivelevich, and M. Tyomkyn, Edge-statistics on large graphs, arXiv:1805.06848 (2018).
Noga Alon and A. V. Kostochka, Induced subgraphs with distinct sizes, Random Structures Algorithms 34 (2009), no. 1, 45–53. MR 2478538, DOI 10.1002/rsa.20250
Noga Alon, Michael Krivelevich, and Benny Sudakov, Induced subgraphs of prescribed size, J. Graph Theory 43 (2003), no. 4, 239–251. MR 1994296, DOI 10.1002/jgt.10117
Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
Maria Axenovich and József Balogh, Graphs having small number of sizes on induced $k$-subgraphs, SIAM J. Discrete Math. 21 (2007), no. 1, 264–272. MR 2299710, DOI 10.1137/05064357X
Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson, 2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction, Ann. of Math. (2) 176 (2012), no. 3, 1483–1543. MR 2979856, DOI 10.4007/annals.2012.176.3.3
A. Bikelis, The estimation of the remainder term in the central limit theorem for samples taken from finite sets, Studia Sci. Math. Hungar. 4 (1969), 345–354 (Russian). MR 254902
Boris Bukh and Benny Sudakov, Induced subgraphs of Ramsey graphs with many distinct degrees, J. Combin. Theory Ser. B 97 (2007), no. 4, 612–619. MR 2325800, DOI 10.1016/j.jctb.2006.09.006
Eshan Chattopadhyay and David Zuckerman, Explicit two-source extractors and resilient functions, STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 670–683. MR 3536605
Gil Cohen, Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs, STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 278–284. MR 3536572, DOI 10.1145/2897518.2897530
D. Conlon, R. Morris, W. Samotij, and D. Saxton, The number of distinct degrees in an induced subgraph of a random graph, personal communication.
P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 19911, DOI 10.1090/S0002-9904-1947-08785-1
P. Erdős, On some of my favourite problems in various branches of combinatorics, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990) Ann. Discrete Math., vol. 51, North-Holland, Amsterdam, 1992, pp. 69–79. MR 1206246, DOI 10.1016/S0167-5060(08)70608-3
P. Erdős and A. Hajnal, On spanned subgraphs of graphs, Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977) Tech. Hochschule Ilmenau, Ilmenau, 1977, pp. 80–96. MR 599767
P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90. MR 111692, DOI 10.1112/jlms/s1-35.1.85
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
P. Erdős and A. Szemerédi, On a Ramsey type theorem, Period. Math. Hungar. 2 (1972), 295–299. MR 325446, DOI 10.1007/BF02018669
Paul Erdős, Some of my favourite problems in various branches of combinatorics, Matematiche (Catania) 47 (1992), no. 2, 231–240 (1993). Combinatorics 92 (Catania, 1992). MR 1275857
Paul Erdős, Some recent problems and results in graph theory, Discrete Math. 164 (1997), no. 1-3, 81–85. The Second Krakow Conference on Graph Theory (Zgorzelisko, 1994). MR 1432220, DOI 10.1016/S0012-365X(96)00044-1
Paul Erdős, Mark Goldberg, János Pach, and Joel Spencer, Cutting a graph into two dissimilar halves, J. Graph Theory 12 (1988), no. 1, 121–131. MR 928742, DOI 10.1002/jgt.3190120113
J. Fox and L. Sauermann, A completion of the proof of the Edge-statistics Conjecture, arXiv:1809.01352 (2018).
P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
Catherine Greenhill, Mikhail Isaev, Matthew Kwan, and Brendan D. McKay, The average number of spanning trees in sparse graphs with given degrees, European J. Combin. 63 (2017), 6–25. MR 3645782, DOI 10.1016/j.ejc.2017.02.003
Thomas Höglund, Sampling from a finite population: a remainder term estimate, Scand. J. Statist. 5 (1978), no. 1, 69–71. MR 471130
M. Kwan and B. Sudakov, Ramsey graphs induce subgraphs of quadratically many sizes, Int. Math. Res. Not. IMRN, to appear, arXiv:1711.02937 (2017).
M. Kwan, B. Sudakov, and T. Tran, Anticoncentration for subgraph statistics, J. London Math. Soc. (to appear).
A. Martinsson, F. Mousset, A. Noever, and M. Trujić, The edge-statistics conjecture for $\ell \ll k^{6/5}$, arXiv:1809.02576 (2018).
B. Narayanan, J. Sahasrabudhe, and I. Tomon, Ramsey graphs induce subgraphs of many different sizes, Combinatorica, to appear, arXiv:1609.01705 (2016).
Bhargav Narayanan and István Tomon, Induced subgraphs with many distinct degrees, Combin. Probab. Comput. 27 (2018), no. 1, 110–123. MR 3734333, DOI 10.1017/S0963548317000256
Hans Jürgen Prömel and Vojtěch Rödl, Non-Ramsey graphs are $c\log n$-universal, J. Combin. Theory Ser. A 88 (1999), no. 2, 379–384. MR 1723803, DOI 10.1006/jcta.1999.2972
Saharon Shelah, Erdős and Rényi conjecture, J. Combin. Theory Ser. A 82 (1998), no. 2, 179–185. MR 1620869, DOI 10.1006/jcta.1997.2845