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
Additional Information
- Matthew Kwan
- Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305
- MR Author ID: 1056015
- Email: mattkwan@stanford.edu
- Benny Sudakov
- Affiliation: Department of Mathematics, ETH, 8092 Zürich, Switzerland
- MR Author ID: 602546
- Email: benjamin.sudakov@math.ethz.ch
- Received by editor(s): March 9, 2018
- Received by editor(s) in revised form: October 9, 2018
- Published electronically: December 7, 2018
- Additional Notes: This research was done while the first-named author was working at ETH Zurich, and is supported in part by SNSF project 178493.
Research supported in part by SNSF grant 200021-175573 - © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 5571-5594
- MSC (2010): Primary 05C55; Secondary 05D10
- DOI: https://doi.org/10.1090/tran/7729
- MathSciNet review: 4014288