The condensation transition in random hypergraph 2-coloring

zbMath1421.68068arXiv1107.2341MaRDI QIDQ5743395

Amin Coja-Oghlan, Lenka Zdeborová

Publication date: 10 May 2019

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

Mathematics Subject Classification ID

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

Related Items

Average-case complexity without the black swans ⋮ Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ A topological dynamical system with two different positive sofic entropies ⋮ On the number of solutions in random hypergraph 2-colouring ⋮ Statistical limits of spiked tensor models ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Panchromatic 3-colorings of random hypergraphs ⋮ 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 ⋮ The asymptotic \(k\)-SAT threshold ⋮ Bounds on threshold probabilities for coloring properties of random hypergraphs ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ On panchromatic colourings of a random hypergraph ⋮ Two-Colorings of a Random Hypergraph ⋮ Random hypergraphs and property B ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ Panchromatic colorings of random hypergraphs ⋮ Spin systems on Bethe lattices ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ The condensation phase transition in random graph coloring ⋮ Colorings of partial Steiner systems and their applications ⋮ Phase Transitions in Discrete Structures ⋮ The number of solutions for random regular NAE-SAT ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Biased landscapes for random constraint satisfaction problems ⋮ On the chromatic number of a random hypergraph

Cites Work

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