Colouring dense random graphs - when can we use the second moment method?

Add to your list(s) Download to your calendar using vCal

• Annika Heckel (University of Oxford)
• Thursday 24 January 2019, 13:00-14:00
• Watson LTB.

If you have a question about this talk, please contact Richard Montgomery.

In a colouring of a graph $G$, no two neighbouring vertices are coloured the same, and the chromatic number $\chi(G)$ is the minimum number of colours where this is possible. By definition any colour class is an independent set, so $\chi(G) \ge n/\alpha(G)$ (where $\alpha(G)$ is the independence number).

For the dense random graph $G(n, 1/2)$, Bollob\’as proved in 1987 that this lower bound is asymptotically sharp. In other words, there is a colouring with average colour class size $(1-o(1)) \alpha(G)$.

Using a combination of the first and second moment method and martingale concentration arguments, this can be sharpened to determine the average colour class size in an optimal colouring up to an additive $o(1)$, but no further. In this talk, we discuss the main obstacles when applying the second moment method to the number of colourings, or more generally to counts of other structures in $G(n,p)$.

If we introduce certain conditions on the colour class sizes in order to circumvent these obstacles, the second moment method can be used to yield some very sharp results. In particular, both the equitable chromatic number (where colour class sizes may differ by at most $1$) and the $(\alpha-2)$-bounded chromatic number (where we avoid colour classes of size $\alpha$ and $\alpha-1$) are concentrated on at most two consecutive values in $G(n, N/2)$.

Joint work with Konstantinos Panagiotou.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTB

Note that ex-directory lists are not shown.