University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Distinct degrees in induced subgraphs

Distinct degrees in induced subgraphs

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

  • UserEoin Long (University of Birmingham)
  • ClockThursday 12 December 2019, 14:00-15:00
  • HouseWatson 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 Ω(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.

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

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.