Hypergraphs: colourability, contiguity and rigidity

dc.contributor.advisor Greenhill, Catherine en_US Ayre, Peter en_US 2022-03-23T10:39:26Z 2022-03-23T10:39:26Z 2019 en_US
dc.description.abstract 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. en_US
dc.language English
dc.language.iso EN en_US
dc.publisher UNSW, Sydney en_US
dc.rights CC BY-NC-ND 3.0 en_US
dc.rights.uri en_US
dc.subject.other Graph en_US
dc.subject.other Colouring en_US
dc.subject.other Hypergraph en_US
dc.subject.other Combinatorics en_US
dc.title Hypergraphs: colourability, contiguity and rigidity en_US
dc.type Thesis en_US
dcterms.accessRights open access
dcterms.rightsHolder Ayre, Peter
dspace.entity.type Publication en_US
unsw.relation.faculty Science
unsw.relation.originalPublicationAffiliation Ayre, Peter, Mathematics & Statistics, Faculty of Science, UNSW en_US
unsw.relation.originalPublicationAffiliation Greenhill, Catherine, Mathematics & Statistics, Faculty of Science, UNSW en_US School of Mathematics & Statistics *
unsw.thesis.degreetype PhD Doctorate en_US
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
public version.pdf
1.02 MB
Resource type