BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability Seminar
SUMMARY:Distinct degrees in induced subgraphs - Eoin Long
(University of Birmingham)
DTSTART:20191212T140000Z
DTEND:20191212T150000Z
UID:TALK3946AT
URL:/talk/index/3946
DESCRIPTION:An important theme of recent research in Ramsey th
eory has been establishing pseudorandomness proper
ties of Ramsey graphs. An N-vertex graph is called
_C-Ramsey_ if it has no homogeneous set of size C
log(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 s
ubgraph with Ω(N^1/2^) distinct degrees. We improv
e this to Ω(N^2/3^)\, which is tight up to the con
stant factor.\n\nWe also show that any N-vertex gr
aph with N > (k−1)(n−1) and n=Ω(k^9^) either conta
ins a homogeneous set of order n or an induced sub
graph 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 an
d Tomon.\n\nJoint work with Matthew Jenssen\, Pete
r Keevash and Liana Yepremyan.
LOCATION:Watson LTB
CONTACT:Eoin Long
END:VEVENT
END:VCALENDAR