Based on a non-rigorous formalism called the “cavity method”, physicists have put forward intriguing predictions on phase transitions in diluted mean-field models, in which the geometry of interactions is induced by a sparse random graph or hypergraph. One example of such a model is the graph coloring problem on the Erdős–Renyi random graph G(n, d n), which can be viewed as the zero temperature case of the Potts antiferromagnet. The cavity method predicts that in addition to the k-colorability phase transition studied intensively in combinatorics, there exists a second phase transition called the condensation phase transition ( in Proc Natl Acad Sci 104:10318–10323, 2007). In fact, there is a conjecture as to the precise location of this phase transition in terms of a certain distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k0.
The notion that for @math close to the (hypothetical) @math -colorability threshold @math it seems difficult to find a @math -coloring of @math algorithmically could be used to construct a candidate one-way function @cite_27 (see also @cite_21 ). This function maps a @math -coloring @math to a random graph @math by linking any two vertices @math with @math with some @math independently. The edge probability @math could be chosen such that the average degree of the resulting graph is close to the @math -colorability threshold. This distribution on graphs is the so-called .
@cite_27 @cite_21
2015596743 2963885173 1610636547 2052952091
In the online F-avoidance edge-coloring game with r colors, a graph on n vertices is generated by randomly adding a new edge at each stage. The player must color each new edge as it appears; the goal is to avoid a monochromatic copy of F. Let N"0(F,r,n) be the threshold function for the number of edges that the player is asymptotically almost surely able to paint before he she loses. Even when F=K"3, the order of magnitude of N"0(F,r,n) is unknown for r>=3. In particular, the only known upper bound is the threshold function for the number of edges in the offline version of the problem, in which an entire random graph on n vertices with m edges is presented to the player to be r edge-colored. We improve the upper bound for the online triangle-avoidance game with r colors, providing the first result that separates the online threshold function from the offline bound for r>=3. This supports a conjecture of Marciniszyn, Spohel, and Steger that the known lower bound is tight for cliques and cycles for all r. In this paper we establish a substantially improved lower bound on the k-color ability threshold of the random graph G(n, m) with n vertices and m edges. The new lower bound is ≈ 1.39 less than the 2k ln (k)-ln (k) first-moment upper bound (and approximately 0.39 less than the 2k ln (k) - ln(k) - 1 physics conjecture). By comparison, the best previous bounds left a gap of about 2+ln(k), unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments [: PNAS 2007]. Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of k-colorings of the random graph. 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. Over the past decade, physicists have developed deep but non-rigorous techniques for studying phase transitions in discrete structures. Recently, their ideas have been harnessed to obtain improved rigorous results on the phase transitions in binary problems such as random @math -SAT or @math -NAESAT (e.g., Coja-Oghlan and Panagiotou: STOC 2013). However, these rigorous arguments, typically centered around the second moment method, do not extend easily to problems where there are more than two possible values per variable. The single most intensely studied example of such a problem is random graph @math -coloring. Here we develop a novel approach to the second moment method in this problem. This new method, inspired by physics conjectures on the geometry of the set of @math -colorings, allows us to establish a substantially improved lower bound on the @math -colorability threshold. The new lower bound is within an additive @math of a simple first-moment upper bound and within @math of the physics conjecture. By comparison, the best previous lower bound left a gap of about @math , unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004].