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_1: Random instances of constraint satisfaction problems (CSPs) appear to be hard for all known algorithms when the number of constraints per variable lies in a certain interval. Contributing to the general understanding of the structure of the solution space of a CSP in the satisfiable regime, we formulate a set of technical conditions on a large family of random CSPs and prove bounds on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and the threshold for an appropriate reconstruction problem on the CSPs. The bounds become asymptoticlally tight as the number of degrees of freedom in each clause diverges. The families are general enough to include commonly studied problems such as random instances of Not-All-Equal SAT, k-XOR formulae, hypergraph 2-coloring, and graph k-coloring. An important new ingredient is a condition involving the Fourier expansion of clauses, which characterizes the class of ...
@cite_17: 
In many random CSPs other than random hypergraph @math -coloring the best current bounds on the thresholds for the existence of solutions derive from the second moment method as well. The most prominent examples are random graph @math -coloring @cite_19 and random @math -SAT @cite_17 . But the second moment argument extends naturally to a range of symmetric' random CSPs @cite_1 . It would be interesting to see if how our techniques can be generalized in order to prove the existence of a condensation transition in these other problems, particularly random graph @math -coloring. However, since even the standard second moment analysis is quite involved in this case of random graph @math -coloring, such a generalization will be technically challenging.