Mathematics – Combinatorics
Scientific paper
2011-07-12
Mathematics
Combinatorics
Scientific paper
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.
Coja-Oghlan Amin
Zdeborová Lenka
No associations
LandOfFree
The condensation transition in random hypergraph 2-coloring does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The condensation transition in random hypergraph 2-coloring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The condensation transition in random hypergraph 2-coloring will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-565880