Distinct degrees in induced subgraphs

Matthew Jenssen, Eoin Long, Peter Keevash, Liana Yepremyan

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
172 Downloads (Pure)


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.

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


  • Ramsey theory
  • Probabilistic methods
  • Induced subgraphs

ASJC Scopus subject areas

  • Applied Mathematics
  • Mathematics(all)


Dive into the research topics of 'Distinct degrees in induced subgraphs'. Together they form a unique fingerprint.

Cite this