The condensation transition in random hypergraph 2-coloring

Abstract

For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method breaks down strictly \emph{before} the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. We expect that our techniques can be extended to other, related problems such as random k-SAT or random graph k-coloring.

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• The Satisfiability Threshold for k-XORSAT
• Reconstruction and Clustering in Random Constraint Satisfaction Problems

Cited by in corpus (15)

• The asymptotic $k$-SAT threshold
• The backtracking survey propagation algorithm for solving random K-SAT problems
• The condensation phase transition in random graph coloring
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Biased landscapes for random Constraint Satisfaction Problems
• Harnessing the Bethe free energy
• Phase transitions in the $q$-coloring of random hypergraphs
• The large deviations of the whitening process in random constraint satisfaction problems
• A positive temperature phase transition in random hypergraph 2-coloring
• Spin systems on Bethe lattices
• Solution space structure of random constraint satisfaction problems with growing domains
• The replica symmetric phase of random constraint satisfaction problems
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• The Rate-Distortion Function and Excess-Distortion Exponent of Sparse Regression Codes with Optimal Encoding
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates