![]() |
![]() |
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 listsContemporary History Seminar Applied Mathematics Seminar Series BravoOther talksSignatures of structural criticality and universality in the cellular anatomy of the brain The percolating cluster is invisible to image recognition with deep learning Provably Convergent Plug-and-Play Quasi-Newton Methods for Imaging Inverse Problems Topological magnons and quantum magnetism [Friday seminar]: Irradiated brown dwarfs in the desert Many-body localization from Hilbert- and real-space points of view |