Distinct degrees in induced subgraphs

Add to your list(s) Download to your calendar using vCal

• Eoin Long (University of Birmingham)
• Thursday 12 December 2019, 14:00-15:00
• Watson LTB.

If you have a question about this talk, please contact Eoin Long.

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 Ω(N^1/2) distinct degrees. We improve this to Ω(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=Ω(k⁹) 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.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTB

Note that ex-directory lists are not shown.