Distinct degrees in induced subgraphs
4th February 2020, 11:00 am – 12:00 pm
Fry Building, 2.04
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 Clog(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 Ω(N1/2) distinct degrees. We improve this to Ω(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=Ω(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.
Joint work with Matthew Jenssen, Peter Keevash and Liana Yepremyan.