The freezing threshold for uniformly random colourings of sparse graphs

-- François Pirot (LISN, Galac)

Time: 14:00 -- Location: LRI, 445

summary: Given a random Δ-regular graph G, it holds that χ(G) ~ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε) Δ / ln Δ, while a greedy algorithm can return a proper k-colouring when k > (1+ε) Δ / ln Δ. One of the reasons that could explain this is that the space of proper k-colourings of a random graph is composed of many far-apart clusters when k < (1−ε) Δ / lnΔ, whence the small probability of success of a local search algorithm to find such a colouring. In contrast, when k > (1+ε) Δ / ln Δ, the space of proper k-colourings is well-connected in many aspects. Namely, in that setting, given a random Δ-regular graph G and a random k-colouring of G, with high probability one can recolour any vertex of G with any colour by recolouring only a sublinear fraction of the vertices.
With respect to proper colourings, sparse graphs share many extremal properties with random graphs. In 2019, Molloy used entropy compression (an algorithmic version of the Lovász Local Lemma introduced in 2010 by Moser and Tardos) to construct a randomised polynomial-time algorithm that yields a proper k-colouring of any triangle-free G of maximum degree Δ, with k = (1+o(1)) Δ / ln Δ as Δ → ∞. In this presentation, I will show that, with high probability, in a uniformly random proper k-colouring of G all but a small fraction of the vertices can be recoloured to any colour by recolouring only their neighbours. The same holds with high probability for every vertex if we require that the girth of G is large enough and recolour its neighbourhood up to a small distance.
This is joint work with Eoin Hurley.

Category: seminars
Tags: Team seminar graphs