Uniformly Random Colourings of Sparse Graphs

Abstract

We analyse uniformly random proper $k$-colourings of sparse graphs with maximum degree $\Delta$ in the regime $\Delta <k\ln k$. This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example of the shattering threshold for random Constraint Satisfaction Problems. We prove a variety of results about the solution space geometry of colourings of fixed graphs, generalising work of Achlioptas, Coja-Oghlan, and Molloy on random graphs, and justifying the performance of stochastic local search algorithms in this regime. Our central proof relies only on elementary techniques, namely the first-moment method and a quantitative induction, yet it strengthens list-colouring results due to Vu, and more recently Davies, Kang, P., and Sereni, and generalises state-of-the-art bounds from Ramsey theory in the context of sparse graphs. It further yields an approximately tight lower bound on the number of colourings, also known as the partition function of the Potts model, with implications for efficient approximate counting.

References in corpus (10)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Algorithmic barriers from phase transitions
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The Johansson--Molloy Theorem for DP-Coloring
• Colouring triangle-free graphs with local list sizes
• Graph structure via local occupancy
• A general framework for hypergraph colouring
• Bounding $\chi$ by a fraction of $\Delta$ for graphs without large cliques