Publication:
Hypergraphs: colourability, contiguity and rigidity

dc.contributor.advisor Greenhill, Catherine en_US
dc.contributor.author Ayre, Peter en_US
dc.date.accessioned 2022-03-23T10:39:26Z
dc.date.available 2022-03-23T10:39:26Z
dc.date.issued 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.identifier.uri http://hdl.handle.net/1959.4/62993
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 https://creativecommons.org/licenses/by-nc-nd/3.0/au/ 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.accessRights.uri https://purl.org/coar/access_right/c_abf2
unsw.identifier.doi https://doi.org/10.26190/unsworks/21321
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
unsw.relation.school School of Mathematics & Statistics *
unsw.thesis.degreetype PhD Doctorate en_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
public version.pdf
Size:
1.02 MB
Format:
application/pdf
Description:
Resource type