Distinct degrees in induced subgraphs
HTML articles powered by AMS MathViewer
- by Matthew Jenssen, Peter Keevash, Eoin Long and Liana Yepremyan PDF
- Proc. Amer. Math. Soc. 148 (2020), 3835-3846 Request permission
Abstract:
An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An $N$-vertex graph is called $C$-Ramsey if it has no homogeneous set of size $C\log N$. A theorem of Bukh and Sudakov, solving a conjecture of Erdős, Faudree, and Sós, shows that any $C$-Ramsey $N$-vertex graph contains an induced subgraph with $\Omega _C(N^{1/2})$ distinct degrees. We improve this to $\Omega _C(N^{2/3})$, which is tight up to the constant factor.
We also show that any $N$-vertex graph with $N > (k-1)(n-1)$ and $n\geq n_0(k) = \Omega (k^9)$ either contains a homogeneous set of order $n$ or an induced subgraph with $k$ distinct degrees. The lower bound on $N$ here is sharp, as shown by an appropriate Turán graph, and confirms a conjecture of Narayanan and Tomon.
References
- Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
- 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
- David Conlon, Jacob Fox, and Benny Sudakov, Recent developments in graph Ramsey theory, Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 49–118. MR 3497267
- D. Conlon, R. Morris, W. Samotij, and D. Saxton, The number of distinct degrees in an induced subgraph of a random graph, unpublished.
- 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
- 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 a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI 10.1090/S0002-9904-1945-08454-7
- 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
- Matthew Kwan and Benny Sudakov, Proof of a conjecture on induced subgraphs of Ramsey graphs, Trans. Amer. Math. Soc. 372 (2019), no. 8, 5571–5594. MR 4014288, DOI 10.1090/tran/7729
- M. Kwan and B. Sudakov, Ramsey graphs induce subgraphs of quadratically many sizes, to appear in Int. Math. Res. Not..
- P. Keevash and E. Long, Forbidden vector-valued intersections, to appear in Proc. Lond. Math. Soc.. arXiv:1706.03740.
- Xin Li, Improved non-malleable extractors, non-malleable codes and independent source extractors, STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 1144–1156. MR 3678258, DOI 10.1145/3055399.3055486
- 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
- Bhargav Narayanan, Julian Sahasrabudhe, and István Tomon, Ramsey graphs induce subgraphs of many different sizes, Combinatorica 39 (2019), no. 1, 215–237. MR 3936198, DOI 10.1007/s00493-017-3755-0
- 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 Jenssen
- Affiliation: School of Mathematicss, University of Birmingham, Birmingham, United Kingdom
- MR Author ID: 1015306
- ORCID: 0000-0003-0026-8501
- Email: m.jenssen@bham.ac.uk
- Peter Keevash
- Affiliation: Mathematical Institute, University of Oxford, Oxford, United Kingdom
- MR Author ID: 670477
- Email: keevash@maths.ox.ac.uk
- Eoin Long
- Affiliation: School of Mathematics, University of Birmingham, Birmingham, United Kingdom
- MR Author ID: 1040049
- Email: e.long@bham.ac.uk
- Liana Yepremyan
- Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois—and—London School of Economics, Department of Mathematics, London, UK
- MR Author ID: 1120553
- Email: lyepre2@uic.edu, l.yepremyan@lse.ac.uk
- Received by editor(s): October 8, 2019
- Received by editor(s) in revised form: February 3, 2020
- Published electronically: May 22, 2020
- Additional Notes: This research was supported in part by ERC Consolidator Grant 647678.
This research was supported by Marie Sklodowska Curie Global Fellowship, H2020-MSCA-IF-2018:846304. - Communicated by: Patricia L. Hersh
- © Copyright 2020 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 148 (2020), 3835-3846
- MSC (2010): Primary 05D10; Secondary 05D40, 05C69
- DOI: https://doi.org/10.1090/proc/15060
- MathSciNet review: 4127829