A positive temperature phase transition in random hypergraph 2-coloring

DOI10.1214/15-AAP1119MaRDI QIDQ303945zbMATH OpenOpenAlexFDO

Authors Victor Bapst, Amin Coja-Oghlan, Felicia Rassmann

Publication date 23 August 2016

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.2190, https://projecteuclid.org/euclid.aoap/1465905006

zbMATH Keywords

phase transitionsdiscrete structurespositive temperaturerandom hypergraphs

Mathematics Subject Classification ID

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

Abstract: Diluted mean-field models are graphical models in which the geometry of interactions is determined by a sparse random graph or hypergraph. Based on a nonrigorous but analytic approach called the "cavity method", physicists have predicted that in many diluted mean-field models a phase transition occurs as the inverse temperature grows from $0$ to $infty$ [Proc. National Academy of Sciences 104 (2007) 10318-10323]. In this paper, we establish the existence and asymptotic location of this so-called condensation phase transition in the random hypergraph $2$-coloring problem.

Recommendations

• The condensation phase transition in random graph coloring
• On the number of solutions in random hypergraph 2-colouring
• The condensation transition in random hypergraph 2-coloring
• The condensation phase transition in random graph coloring
• Phase transitions in the \(q\)-coloring of random hypergraphs

Cites work

• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Antiferromagnetic Potts model on the Erdős-Rényi random graph
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Information, Physics, and Computation
• On the 2-colorability of random hypergraphs
• The condensation phase transition in random graph coloring

Cited in

(14)

• Rigid colorings of hypergraphs and contiguity
• Charting the replica symmetric phase
• Phase transitions in the \(q\)-coloring of random hypergraphs
• 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
• The condensation transition in random hypergraph 2-coloring
• Harnessing the Bethe free energy
• On the number of solutions in random graph \(k\)-colouring
• The number of solutions for random regular NAE-SAT
• Phase transition in the spanning-hyperforest model on complete hypergraphs
• Biased landscapes for random constraint satisfaction problems
• On the Potts antiferromagnet on random graphs
• Bicolouring random hypergraphs

This page was built for publication: A positive temperature phase 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 Q303945)