The condensation transition in random hypergraph 2-coloring

zbMATH Open1421.68068arXiv1107.2341MaRDI QIDQ5743395FDOQ5743395

Authors: Amin Coja-Oghlan, Lenka Zdeborová 

Publication date: 10 May 2019

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.

Full work available at URL: https://arxiv.org/abs/1107.2341

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

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)

Cites Work

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

Cited In (36)

• Spin systems on Bethe lattices
• Algorithmic obstructions in the random number partitioning problem
• Statistical limits of spiked tensor models
• Bounds on threshold probabilities for coloring properties of random hypergraphs
• Random hypergraphs and property B
• 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
• Phase transitions in discrete structures
• Panchromatic 3-colorings of random hypergraphs
• Estimating the \(r\)-colorability threshold for a random hypergraph
• Hypergraph coloring up to condensation
• On panchromatic colourings of a random hypergraph
• Satisfiability threshold for random regular \textsc{nae-sat}
• Circular coloring of random graphs: statistical physics investigation
• The large deviations of the whitening process in random constraint satisfaction problems
• Phase transitions in the \(q\)-coloring of random hypergraphs
• Average-case complexity without the black swans
• 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 asymptotics of the clustering transition for random constraint satisfaction problems
• The asymptotic \(k\)-SAT threshold
• 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)