Phase transitions in the -coloring of random hypergraphs
arXiv:1707.01983 · doi:10.1088/1751-8121/aa9529
Abstract
We study in this paper the structure of solutions in the random hypergraph coloring problem and the phase transitions they undergo when the density of constraints is varied. Hypergraph coloring is a constraint satisfaction problem where each constraint includes variables that must be assigned one out of colors in such a way that there are no monochromatic constraints, i.e. there are at least two distinct colors in the set of variables belonging to every constraint. This problem generalizes naturally coloring of random graphs () and bicoloring of random hypergraphs (), both of which were extensively studied in past works. The study of random hypergraph coloring gives us access to a case where both the size of the domain of the variables and the arity of the constraints can be varied at will. Our work provides explicit values and predictions for a number of phase transitions that were discovered in other constraint satisfaction problems but never evaluated before in hypergraph coloring. Among other cases we revisit the hypergraph bicoloring problem () where we find that for and the colorability threshold is not given by the one-step-replica-symmetry-breaking analysis as the latter is unstable towards more levels of replica symmetry breaking. We also unveil and discuss the coexistence of two different 1RSB solutions in the case of , . Finally we present asymptotic expansions for the density of constraints at which various phase transitions occur, in the limit where and/or diverge.
arXiv comment31 pages, 7 figures
References in corpus (30)
- Theoretical perspective on the glass transition and amorphous materials
- Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Phase Transitions in the Coloring of Random Graphs
- Glass and Jamming Transitions: From Exact Results to Finite-Dimensional Descriptions
- Clustering of solutions in the random satisfiability problem
- Coloring random graphs
- On the nature of the low-temperature phase in discontinuous mean-field spin glasses
- Reconstruction on trees and spin glass transition
- Glass models on Bethe lattices
- A variational description of the ground state structure in random satisfiability problems
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- On the dynamics of the glass transition on Bethe lattices
- Information-theoretic thresholds from the cavity method
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
- Statistical and computational phase transitions in spiked tensor estimation
- Robust reconstruction on trees is determined by the second eigenvalue
- Reconstruction of Random Colourings
- Catching the k-NAESAT Threshold
- The condensation transition in random hypergraph 2-coloring
- The condensation phase transition in random graph coloring
- The 3-SAT problem with large number of clauses in -replica symmetry breaking scheme
- The large deviations of the whitening process in random constraint satisfaction problems
- The marginally stable Bethe lattice spin glass revisited
- Bicoloring Random Hypergraphs
- A positive temperature phase transition in random hypergraph 2-coloring
- Circular Coloring of Random Graphs: Statistical Physics Investigation
- Reconstruction of colourings without freezing
Cited by in corpus (11)
- Typology of phase transitions in Bayesian inference problems
- Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
- Biased landscapes for random Constraint Satisfaction Problems
- Learning from Survey Propagation: a Neural Network for MAX-E--SAT
- Random Recursive Hypergraphs
- The asymptotics of the clustering transition for random constraint satisfaction problems
- Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
- Satisfiability Thresholds for Regular Occupation Problems
- Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs
- Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
- Interacting Copies of Random Constraint Satisfaction Problems