BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability seminar
SUMMARY:Colouring dense random graphs - when can we use th
e second moment method? - Annika Heckel (Universit
y of Oxford)
DTSTART:20190124T130000Z
DTEND:20190124T140000Z
UID:TALK3491AT
URL:/talk/index/3491
DESCRIPTION:In a colouring of a graph $G$\, no two neighbourin
g vertices are coloured the same\, and the chromat
ic number $\\chi(G)$ is the minimum number of colo
urs where this is possible. By definition any colo
ur class is an independent set\, so $\\chi(G) \\ge
n/\\alpha(G)$ (where $\\alpha(G)$ is the independ
ence number).\n\nFor the dense random graph $G(n\,
1/2)$\, Bollob\\'as proved in 1987 that this lowe
r bound is asymptotically sharp. In other words\,
there is a colouring with average colour class siz
e $(1-o(1)) \\alpha(G)$.\n\nUsing a combination of
the first and second moment method and martingale
concentration arguments\, this can be sharpened t
o determine the average colour class size in an op
timal colouring up to an additive $o(1)$\, but no
further. In this talk\, we discuss the main obstac
les when applying the second moment method to the
number of colourings\, or more generally to counts
of other structures in $G(n\,p)$.\n\nIf we introd
uce certain conditions on the colour class sizes i
n order to circumvent these obstacles\, the second
moment method can be used to yield some very shar
p results. In particular\, both the equitable chro
matic number (where colour class sizes may differ
by at most $1$) and the $(\\alpha-2)$-bounded chro
matic number (where we avoid colour classes of siz
e $\\alpha$ and $\\alpha-1$) are concentrated on a
t most two consecutive values in $G(n\, N/2)$.\n\n
Joint work with Konstantinos Panagiotou.
LOCATION:Watson LTB
CONTACT:Richard Montgomery
END:VEVENT
END:VCALENDAR