![]() |
![]() |
University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Colouring dense random graphs - when can we use the second moment method?
![]() Colouring dense random graphs - when can we use the second moment method?Add to your list(s) Download to your calendar using vCal
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:Note that ex-directory lists are not shown. |
Other listsTopology and Dynamics seminar Cond. Mat. seminar Applied Topology ColloquiumOther talksProofs of Turán's theorem Wave turbulence in the Schrödinger-Helmholtz equation An introduction to τ-exceptional sequences Waveform modelling and the importance of multipole asymmetry in Gravitational Wave astronomy The tragic destiny of Mileva Marić Einstein TBA |