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 applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability.
@cite_19: Given d ?? (0,??) let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d n) is either kd or kd + 1 almost surely.
@cite_2: A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k, n, p) be a random k-uniform hypergraph on a vertex set V of cardinality n, where each k-subset of V is an edge of H with probability p, independently of all other k-subsets. Let m = p(????) denote the expected number of edges in H. Let us say that a sequence of events En holds with high probability (w.h.p.) if limn → ∞ Pr[En] = 1. It is easy to show that if m = c2kn then w.h.p H is not 2-colorable for c > ln 2 2. We prove that there exists a constant c > 0 such that if m = (c2k k)n, then w.h.p H is 2-colorable.
@cite_3: Many NP-complete constraint satisfaction problems appear to undergo a “phase transition” from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2-colorability (Property B) and random Not-All-Equal @math -SAT is @math . As a corollary, we establish that the threshold for random @math -SAT is of order @math , resolving a long-standing open problem.
@cite_17: 
The two inequalities in ) state the best previous bounds on the threshold for hypergraph @math -colorability from the paper of Achlioptas and Moore @cite_3 , which provided the prototype for the second moment analyses in other sparse random CSPs (e.g., @cite_19 @cite_17 ). Since the second moment method is non-constructive, there is the separate algorithmic question: for what densities can a @math -coloring of a random hypergraph be constructed in polynomial time ? The best current algorithm is known to succeed up to @math for some constant @math , i.e., up to a factor of about @math below the @math -colorability threshold @cite_2 .