![]() |
![]() |
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 listsGeometry and Mathematical Physics seminar School of Metallurgy and Materials Colloquia Algebra seminarOther talks[Friday seminar]: Irradiated brown dwarfs in the desert Signatures of structural criticality and universality in the cellular anatomy of the brain Provably Convergent Plug-and-Play Quasi-Newton Methods for Imaging Inverse Problems The percolating cluster is invisible to image recognition with deep learning |