Hypergraphs: colourability, contiguity and rigidity

Download files
Access & Terms of Use
open access
Copyright: Ayre, Peter
Constraint satisfaction problems (CSPs) capture some of the most conceptually basic, yet difficult questions in mathematics. A CSP is defined by a set of variables which are related via a set of constraint equations. The question is then asked whether a particular instance admits an assignment of variables that simultaneously satisfies all of the given constraints. Such problems form the most basic building blocks of complex systems and are at the heart of a broad range of scientific problems. The colouring problem in graph theory is a canonical example of a constraint satisfaction problem and has been extensively studied since the 1850s. Despite this, some fundamental questions remain. In particular, precisely determining the distribution of the chromatic number a random graph has been notoriously difficult. The central problem of study in this thesis is the colourability of random hypergraphs with a linear number of edges. We determine the chromatic number for all but a vanishing proportion of edge densities, meaning that for nearly all cases, the problem is effectively closed. The proof relies heavily on intuition gleamed from a highly ingenious but non-rigorous formalism from statistical physics known as the cavity method. Further, the cavity method makes several other conjectures as to the geometry of the solution space, and in particular, presents evidence of “freezing” in the geometry of the solution space. We verify the location and behaviour of the “rigidity threshold” for hypergraph colouring, marking the point at which a large proportion of vertices become frozen to a particular colour. Notably, this threshold has been hypothesised to be the cause of the algorithmic barrier faced by naive algorithms.
Persistent link to this record
Link to Publisher Version
Link to Open Access Version
Additional Link
Ayre, Peter
Greenhill, Catherine
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
Resource Type
Degree Type
PhD Doctorate
UNSW Faculty
download public version.pdf 1.02 MB Adobe Portable Document Format
Related dataset(s)