![]() |
![]() |
University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Distinct degrees in induced subgraphs
![]() Distinct degrees in induced subgraphsAdd to your list(s) Download to your calendar using vCal
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. This talk is included in these lists:Note that ex-directory lists are not shown. |
Other listsTest Bravo Cold atomsOther talksProofs of Turán's theorem The tragic destiny of Mileva Marić Einstein Life : it’s out there, but what and why ? TBA TBA TBA |