The condensation transition in random hypergraph 2-coloring

MaRDI QIDQ5743395zbMATH OpenFDO

Authors Amin Coja-Oghlan, Lenka Zdeborová

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1107.2341, https://dl.acm.org/citation.cfm?id=2095138

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

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.

Recommendations

• The condensation phase transition in random graph coloring
• The condensation phase transition in random graph coloring
• A positive temperature phase transition in random hypergraph 2-coloring
• Hypergraph coloring up to condensation
• Phase transitions in the \(q\)-coloring of random hypergraphs

Cites work

• Component structure in the evolution of random hypergraphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• Hunting for sharp thresholds
• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Pairs of SAT-assignments in random Boolean formulæ
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Random k-SAT: A tight threshold for moderately growing k
• Random k-sat: the limiting probability for satisfiability for moderately growing k
• Random subcubes as a toy model for constraint satisfaction problems
• Reconstruction and clustering in random constraint satisfaction problems
• Sharp thresholds of graph properties, and the k-sat problem
• The 3-XORSAT threshold.
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The two possible values of the chromatic number of a random graph
• Two‐coloring random hypergraphs

Cited in

(37)

• Panchromatic colorings of random hypergraphs
• Spin systems on Bethe lattices
• The number of solutions for random regular NAE-SAT
• Statistical limits of spiked tensor models
• Estimating the r-colorability threshold for a random hypergraph
• Random hypergraphs and property B
• On the chromatic number of a random hypergraph
• Average-case complexity without the black swans
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• On the number of solutions in random hypergraph 2-colouring
• Panchromatic 3-colorings of random hypergraphs
• Colorings of partial Steiner systems and their applications
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Phase transitions in discrete structures
• The condensation phase transition in random graph coloring
• A positive temperature phase transition in random hypergraph 2-coloring
• The number of satisfying assignments of random regular k-SAT formulas
• The large deviations of the whitening process in random constraint satisfaction problems
• Circular coloring of random graphs: statistical physics investigation
• Phase transitions in the \(q\)-coloring of random hypergraphs
• The replica symmetric phase of random constraint satisfaction problems
• Biased landscapes for random constraint satisfaction problems
• A topological dynamical system with two different positive sofic entropies
• Hypergraph coloring up to condensation
• On panchromatic colourings of a random hypergraph
• Two-colorings of a random hypergraph
• Bicolouring random hypergraphs
• Satisfiability threshold for random regular \textsc{nae-sat}
• The condensation phase transition in random graph coloring
• One-step replica symmetry breaking of random regular NAE-SAT. II
• Algorithmic obstructions in the random number partitioning problem
• On the structure of the set of panchromatic colorings of a random hypergraph
• Bounds on threshold probabilities for coloring properties of random hypergraphs
• Frozen 1-RSB structure of the symmetric Ising perceptron
• Searching for (sharp) thresholds in random structures: where are we now?
• Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k 3
• The asymptotic k-SAT threshold

This page was built for publication: The condensation transition in random hypergraph 2-coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743395)