The freezing threshold for uniformly random colourings of sparse graphs
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.