×

Distinct degrees in induced subgraphs. (English) Zbl 1444.05140

Summary: An important theme of recent research in Ramsey theory has been to establish 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 B. Bukh and B. Sudakov [J. Comb. Theory, Ser. B 97, No. 4, 612–619 (2007; Zbl 1120.05057)], 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 B. Narayanan and I. Tomon [Comb. Probab. Comput. 27, No. 1, 110–123 (2018; Zbl 1378.05127)].

MSC:

05D10 Ramsey theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Bollob\'{a}s, B\'{e}la, Extremal graph theory, London Mathematical Society Monographs 11, xx+488 pp. (1978), Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York · Zbl 1099.05044
[2] Bukh, Boris; Sudakov, Benny, Induced subgraphs of Ramsey graphs with many distinct degrees, J. Combin. Theory Ser. B, 97, 4, 612-619 (2007) · Zbl 1120.05057 · doi:10.1016/j.jctb.2006.09.006
[3] Conlon, David; Fox, Jacob; Sudakov, Benny, Recent developments in graph Ramsey theory. Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser. 424, 49-118 (2015), Cambridge Univ. Press, Cambridge · Zbl 1352.05123
[4] CMSS D. Conlon, R. Morris, W. Samotij, and D. Saxton, The number of distinct degrees in an induced subgraph of a random graph, unpublished.
[5] Erd\H{o}s, Paul, Some of my favourite problems in various branches of combinatorics, Matematiche (Catania), 47, 2, 231-240 (1993) (1992) · Zbl 0797.05001
[6] Erd\"{o}s, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53, 292-294 (1947) · Zbl 0032.19203 · doi:10.1090/S0002-9904-1947-08785-1
[7] Erd\"{o}s, P., On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 51, 898-902 (1945) · Zbl 0063.01270 · doi:10.1090/S0002-9904-1945-08454-7
[8] Erd\"{o}s, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · Zbl 0012.27010
[9] Erd\H{o}s, P.; Szemer\'{e}di, A., On a Ramsey type theorem, Period. Math. Hungar., 2, 295-299 (1972) · Zbl 0242.05122 · doi:10.1007/BF02018669
[10] Kwan, Matthew; Sudakov, Benny, Proof of a conjecture on induced subgraphs of Ramsey graphs, Trans. Amer. Math. Soc., 372, 8, 5571-5594 (2019) · Zbl 1423.05106 · doi:10.1090/tran/7729
[11] KS2 M. Kwan and B. Sudakov, Ramsey graphs induce subgraphs of quadratically many sizes, to appear in Int. Math. Res. Not..
[12] KL P. Keevash and E. Long, Forbidden vector-valued intersections, to appear in Proc. Lond. Math. Soc.. 1706.03740.
[13] Li, Xin, 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, 1144-1156 (2017), ACM, New York · Zbl 1370.94527 · doi:10.1145/3055399.3055486
[14] Narayanan, Bhargav; Tomon, Istv\'{a}n, Induced subgraphs with many distinct degrees, Combin. Probab. Comput., 27, 1, 110-123 (2018) · Zbl 1378.05127 · doi:10.1017/S0963548317000256
[15] Narayanan, Bhargav; Sahasrabudhe, Julian; Tomon, Istv\'{a}n, Ramsey graphs induce subgraphs of many different sizes, Combinatorica, 39, 1, 215-237 (2019) · Zbl 1438.05237 · doi:10.1007/s00493-017-3755-0
[16] Pr\"{o}mel, Hans J\"{u}rgen; R\"{o}dl, Vojt\v{e}ch, Non-Ramsey graphs are \(c\log n\)-universal, J. Combin. Theory Ser. A, 88, 2, 379-384 (1999) · Zbl 0934.05090 · doi:10.1006/jcta.1999.2972
[17] Shelah, Saharon, Erd\H{o}s and R\'{e}nyi conjecture, J. Combin. Theory Ser. A, 82, 2, 179-185 (1998) · Zbl 0906.05048 · doi:10.1006/jcta.1997.2845
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.