Georgia Institute of Technology College of Sciences

We will discuss proper q-colourings of sparse, bounded degree graphs when the maximum degree is near the so-called shattering threshold. This threshold, first identified in the statistical physics literature, coincides with the point at which all known efficient colouring algorithms fail and it has been hypothesized that the geometry of the solution space (the space of proper colourings) is responsible. This hypothesis is a cousin of the Overlap-Gap property of Gamarnik ‘21. Significant evidence for this picture was provided by Achlioptos and Coja-Oghlan ‘08, who drew inspiration from statistical physics, but their work only explains the performance of algorithms on random graphs (average-case complexity). We extend their work beyond the random setting by proving that the geometry of the solution space is well behaved for all graphs below the “shattering threshold”. This follows from an original result about the structure of uniformly random colourings of fixed graphs. Joint work with François Pirot.