Rigid colorings of hypergraphs and contiguity
From MaRDI portal
Publication:5233753
DOI10.1137/18M1207211zbMATH Open1420.05159arXiv1808.04060WikidataQ127300456 ScholiaQ127300456MaRDI QIDQ5233753FDOQ5233753
Authors: Peter Ayre, Catherine Greenhill 
Publication date: 6 September 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: We consider the problem of -colouring a -uniform random hypergraph, where , and determine the rigidity threshold. For edge densities above the rigidity threshold, we show that almost all solutions have a linear number of vertices that are linearly frozen, meaning that they cannot be recoloured by a sequence of colourings that each change the colour of a sublinear number of vertices. When the edge density is below the threshold, we prove that all but a vanishing proportion of the vertices can be recoloured by a sequence of colourings that recolour only one vertex at a time. This change in the geometry of the solution space has been hypothesised to be the cause of the algorithmic barrier faced by naive colouring algorithms. Our calculations verify predictions made by statistical physicists using the non-rigorous cavity method. The traditional model for problems of this type is the random colouring model, where a random hypergraph is chosen and then a random colouring of that hypergraph is selected. However, it is often easier to work with the planted model, where a random colouring is selected first, and then edges are randomly chosen which respect the colouring. As part of our analysis, we show that up to the condensation phase transition, the random colouring model is contiguous with respect to the planted model. This result is of independent interest.
Full work available at URL: https://arxiv.org/abs/1808.04060
Recommendations
Cites Work
- On the Lambert \(w\) function
- Title not available (Why is that?)
- Random graphs.
- The two possible values of the chromatic number of a random graph
- On the freezing of variables in random constraint satisfaction problems
- Coloring random graphs
- A positive temperature phase transition in random hypergraph 2-coloring
- The condensation phase transition in random graph coloring
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- The freezing threshold for \(k\)-colourings of a random graph
- On the solution-space geometry of random constraint satisfaction problems
- Almost all cubic graphs are Hamiltonian
- Survey propagation: An algorithm for satisfiability
- On the chromatic number of a random hypergraph
- Quiet planting in the locked constraint satisfaction problems
- Lower bounds on the chromatic number of random graphs
- Planting colourings silently
- The stripping process can be slow. I.
- Frozen variables in random Boolean constraint satisfaction problems
- Phase transitions in the \(q\)-coloring of random hypergraphs
- The large deviations of the whitening process in random constraint satisfaction problems
- The freezing threshold for \(k\)-colourings of a random graph
- On the number of solutions in random graph \(k\)-colouring
Cited In (8)
- On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
- On the structure of the set of panchromatic colorings of a random hypergraph
- The freezing threshold for \(k\)-colourings of a random graph
- Estimating the \(r\)-colorability threshold for a random hypergraph
- The replica symmetric phase of random constraint satisfaction problems
- On the connectivity of proper colorings of random graphs and hypergraphs
- On the maximal cut in a random hypergraph
- The freezing threshold for \(k\)-colourings of a random graph
This page was built for publication: Rigid colorings of hypergraphs and contiguity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233753)
