Bicolouring random hypergraphs

DOI10.1088/0305-4470/36/43/026MaRDI QIDQ5696395zbMATH OpenOpenAlexWikidataFDO

Authors Tommaso Castellani, Vincenzo Napolano, Federico Ricci-Tersenghi, Riccardo Zecchina

Publication date 18 October 2005

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0306369

zbMATH Keywords

bicolouring random hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Symbolic computation and algebraic computation (68W30) Equilibrium statistical mechanics (82B99)

Abstract: We study the problem of bicoloring random hypergraphs, both numerically and analytically. We apply the zero-temperature cavity method to find analytical results for the phase transitions (dynamic and static) in the 1RSB approximation. These points appear to be in agreement with the results of the numerical algorithm. In the second part, we implement and test the Survey Propagation algorithm for specific bicoloring instances in the so called HARD-SAT phase.

Recommendations

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

Cited in

(8)

• On the freezing of variables in random constraint satisfaction problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Random Bichromatic Matchings
• Phase transitions in the \(q\)-coloring of random hypergraphs
• Biased landscapes for random constraint satisfaction problems
• Satisfiability thresholds for regular occupation problems
• Satisfiability threshold for random regular \textsc{nae-sat}
• Satisfiability thresholds for regular occupation problems

This page was built for publication: Bicolouring random hypergraphs

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