Distinct degrees in induced subgraphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Oxford

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 logN. 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 ΩC(N1/2) distinct degrees. We improve this to ΩC(N2/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 ≥ n0(k) = Ω(k9) 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.

Details

Original languageEnglish
Pages (from-to)3835-3846
Number of pages12
JournalProceedings of the American Mathematical Society
Volume148
Issue number9
Early online date22 May 2020
Publication statusPublished - Sep 2020

Keywords

  • Ramsey theory, Probabilistic methods, Induced subgraphs

ASJC Scopus subject areas