BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Distinct degrees and homogeneous sets - Eoin Long
(Birmingham)
DTSTART;TZID=Europe/London:20220602T143000
DTEND;TZID=Europe/London:20220602T153000
UID:TALK175313AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/175313
DESCRIPTION:In this talk I will discuss some recent work exami
ning the extremal relationship between two well-st
udied graph parameters: the order of the largest h
omogeneous set in a graph G and the maximal number
of distinct degrees appearing in an induced subgr
aph of G\, denoted respectively by hom (G) and f(G
).\n\nOur main theorem improves estimates due to B
ukh and Sudakov and to Narayanan and Tomon and sho
ws that if G is an n-vertex graph with hom (G) at
least n^{1/2} then f(G) > ( n / hom (G) )^{1 - o(1
)}. The bound here is sharp up to the o(1)-term\,
and asymptotically solves a conjecture of Narayana
n and Tomon. In particular\, this implies that max
{ hom (G)\, f(G) } > n^{1/2 -o(1)} for any n-vert
ex graph G\, which is also sharp.\n\nThe relations
hip between these parameters is known to change wh
en hom (G) < n^{1/2}. I hope to discuss the suspec
ted relationship in this other region\, along with
supporting results.\n\nJoint work with Laurentiu
Ploscaru.\n
LOCATION:MR14
CONTACT:
END:VEVENT
END:VCALENDAR