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

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) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

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

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• Component structure in the evolution of random hypergraphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• 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

(36)

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

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)