PaperlayerView exact revision on arXiv

Source-linked AI summary

The condensation phase transition in random graph coloring

Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Rassmann, Dan Vilenchik

arXiv:1404.5513v1cs.DMmath.COmath.PR

TL;DR

Locating random constraint-satisfaction thresholds precisely remains an open problem, and near-threshold instances are regarded as challenging algorithmic benchmarks. This paper combines two proof threads to establish the predicted condensation location in random graph coloring and give a combinatorial explanation of the transition.

  • Problem

    The location of random graph k-colorability thresholds remains open, while near-threshold instances are regarded as challenging algorithmic benchmarks.

    Source: §1 · p. 1

  • Method

    The proof identifies a critical degree and a frozen fixed point, interprets the fixed point combinatorially, and links the two to the unique zero of equation (2.6).

    Source: §4 · p. 6

  • Results

    The paper rigorously establishes the precise condensation location predicted by the cavity method in random graph coloring.

    Source: §2 · p. 2

  • Takeaways & Limitations

    The proof also provides a direct combinatorial explanation of how the condensation phase transition comes about.

    Source: §2 · p. 2

    Existence of Φ_k(d) for all d,k remains unproved and may be difficult to establish; proving it would imply convergence of d_k-col(n).

    Source: §2.1 · p. 2

Abstract

from arXiv · show

Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random $k$-SAT or random graph $k$-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called "condensation" [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the $k$-colorability threshold as well as to the performance of message passing algorithms. In random graph $k$-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for $k$ exceeding a certain constant $k_0$.

1. INTRODUCTION

Research on random constraint satisfaction links solution thresholds with algorithmic difficulty, while the cavity method predicts a condensation transition shortly before the threshold. This introduction frames the challenge of locating thresholds and the structural and algorithmic questions surrounding condensation.

1. INTRODUCTION

  • Experiments motivated hypotheses that random k-SAT and graph k-coloring have satisfiability thresholds and that instances near them are algorithmically challenging.The cited work describes difficulty through various measures, not formal computational complexity.Source: §1 · p. 1
  • Proving whether the random graph k-colorability sharp-threshold sequence converges to one number and determining its location remain open problems.The sequence marks where the probability of k-colorability drops from 1 to 0.Source: §1 · p. 1
  • Frozen clusters arise before the solution threshold, and their average-degree onset roughly matches where efficient algorithms are provably able to find solutions.Physicists proposed message-passing algorithms for clustered solution spaces, but satisfactory analysis remains elusive.Source: §1 · p. 1
  • The cavity method predicts a condensation transition shortly before the solution threshold, when a sub-exponential number of clusters contain a constant fraction of all solutions.Before condensation, each cluster contains only an exponentially small fraction of solutions.Source: §1 · pp. 1–2

2. RESULTS

For k above a constant k0, the paper proves that random graph coloring has a condensation transition at the location predicted by the cavity method. It gives a precise transition location and relates it to the changing sizes of coloring clusters.

2. RESULTS

  • For k ≥ k0, the paper proves a condensation transition at the cavity method’s predicted location, the first rigorous determination of an exact location of this kind.The proof also gives a direct combinatorial explanation of the transition.Source: §2 · p. 2

2.1. Catching a sharp threshold.

  • For d ≥ (2k − 1) ln k − 2, Fd,k has precisely one frozen fixed point, and the theorem’s function has a unique zero dk,cond in [(2k − 1) ln k − 2, (2k − 1) ln k − 1].A measure is called frozen when at least 2/3 of its mass is on the simplex vertices.Source: §2.1 · p. 3
  • For 0 < d < dk,cond, Φk(d) is smooth and equals k·(1 − 1/k)^(d/2); the theorem identifies a phase transition at dk,cond.The paper defines a phase transition here by non-analyticity of Φk.Source: §2.1 · pp. 2–3
  • The precise transition location is one number rather than a sharp-threshold sequence that might vary with n, and the fixed point has a combinatorial interpretation as a discrete probability distribution.For large k, dk,cond = (2k − 1) ln k − 2 ln 2 + εk, where εk → 0.Source: §2.1 · p. 4

2.2. The cluster size.

  • For d between (2k − 1) ln k − 2 and dk,cond, the total number of k-colorings exceeds a random coloring’s cluster size by at least exp[n(Σk(d) + o(1))] w.h.p.The cluster is defined by overlap: each color agrees on at least 0.51/k of vertices; Σk is positive and decreases toward zero at dk,cond.Source: §2.2 · p. 4
  • As d approaches dk,cond, Σk(d) tends to zero, and with non-vanishing probability the gap between total colorings and one cluster is at most exp[n(Σk(d) + o(1))].The random coloring is considered conditional on the graph being k-colorable, a condition the paper says is harmless below dk,cond.Source: §2.2 · p. 4

3. DISCUSSION AND RELATED WORK

The discussion places the condensation result alongside work on the colorability threshold, planted models, and message-passing algorithms. It also explains how the proof connects the cavity-method fixed point to coloring geometry and how this exact result fits into the physics literature.

3.1. The k-colorability threshold.

  • Theorem 2.1 improves the lower bound from [10] by determining its error term through d_k,cond, while the physics prediction keeps this distinct from the colorability threshold.The paper also identifies d_k,cond as a single value rather than a threshold sequence that may vary with n.Source: §3.1 · p. 5

3.2. “Quiet planting?”

  • The planted distribution and G(n,d/n) are interchangeable in a certain precise sense iff Φk(d)=k(1−1/k)^(d/2); Theorem 2.1 shows they are not interchangeable at the k-colorability threshold.Experimental evidence that coloring G(n,d/n) is difficult at or near dk−col is inconclusive about finding a k-coloring in the planted model.Source: §3.2 · p. 5

3.3. Message passing algorithms.

  • Belief Propagation Guided Decimation repeatedly fixes a vertex color using estimated marginals, but its success depends on the fixed-point iteration approximating those marginals.The proposed link between approximation quality and absence of condensation is non-rigorous; this paper treats the t=0 case, while extension to t>0 remains open.Source: §3.3 · pp. 5–6

3.4. The physics perspective.

  • Theorem 2.1 is the first result to locate condensation exactly in a diluted mean-field model, improving on the hypergraph 2-coloring result’s asymptotic error bound.The proof builds on prior coloring-geometry techniques and introduces a novel rigorous connection between the distributional fixed-point problem and coloring geometry.Source: §3.4 · p. 6

4. OUTLINE

The proof identifies a critical degree through two parallel threads: locating a change in the coloring-count behavior and interpreting a frozen fixed point through a random tree process. It then connects the tree process to planted-graph cluster sizes to show that the critical degree equals the predicted condensation degree.

4. OUTLINE

  • The proof has two threads: identify a critical degree satisfying the theorem’s conditions, then interpret the frozen fixed point combinatorially and show the degrees coincide.The first thread extends ideas for random hypergraph 2-coloring; the fixed-point interpretation and the argument joining the threads are novel.Source: §4 · p. 6

4.1. The first thread.

  • The critical degree is finite and bounded above by (2k−1)ln k, and the first thread establishes its existence as a phase-transition point.The upper bound follows because graphs above that degree are uncolorable with high probability, making the coloring-count limit zero.Source: §4.1 · p. 7
  • For d<d_k,crit, a randomly chosen coloring’s cluster is exponentially smaller than the total coloring count; d_k,crit is where their orders match.This cluster-size behavior supplies the combinatorial interpretation sought for the critical degree.Source: §4.1 · p. 7
  • When Φ_k(d)=k(1−1/k)^(d/2), the planted model approximates sampling a random graph and then a uniform coloring, enabling a planted-model estimate of cluster size.The outline relates the suitably scaled planted-model cluster size to that in G(n,d/n).Source: §4.1 · p. 7

4.2. The second thread.

  • The second thread models legal colorings on a decorated multi-type Galton–Watson tree, whose root-color distribution gives a combinatorial interpretation of the fixed point.Types encode a distinguished color and available-color set; legal colorings must respect the available set at each vertex.Source: §4.2 · pp. 8–9
  • For d in the stated high-degree interval, the fixed-point analysis gives a unique frozen fixed point and a unique zero d_k,cond of Σ_k.The associated branching process is subcritical, and the proof connects its tree distribution to planted-graph cluster size using Warning Propagation, yielding d_k,crit=d_k,cond.Source: §4.2 · p. 9, §4.3 · p. 9

5. GROUNDWORK: THE FIRST AND THE SECOND MOMENT METHOD

This section develops first- and second-moment bounds on the number of colorings, then uses them in the proof of Proposition 4.2 to establish a phase transition at d_k,crit.

5.1. The first moment upper bound.

  • For G(n,m), the expected number of k-colorings is Θ(k^n(1−1/k)^m).The proof lower-bounds the expectation using balanced colorings, each of which is a coloring with probability Ω((1−1/k)^m).Source: §5.1 · p. 10
  • For any c > 0, lim sup as n → ∞ of E[Z_k(G(n, c/n))^(1/n)] is at most k(1 − 1/k)^(c/2).Source: §5.1 · p. 10

5.2. The second moment lower bound.

  • If the second-moment condition holds throughout an interval below d*, then Lemma 5.7 implies d_k,crit ≥ d*.The condition is satisfied for d ≤ (2k−1) ln k − 2 ln 2 − ε_k, with ε_k=o_k(1).Source: §5.2 · p. 11
  • Below the stated range, the tame-coloring second-moment argument yields at least ξ^n k-colorings with high probability.The result is stated for any d<hat d under the preceding second-moment assumptions.Source: §5.2 · pp. 11–12

5.3. Proof of Proposition 4.2.

  • An expected-count deficit at d1 persists at every d2>d1, with a positive gap from the first-moment bound.The gap depends on δ, k, d1, and d2.Source: §5.3 · p. 12
  • The proof of Proposition 4.2 establishes that d_k,crit is a phase transition by contradiction with the assumed analyticity of Φ_k(d).The argument uses that Φ_k(d) equals k(1−1/k)^(d/2) below d_k,crit, which would force the same expression across the critical point if it were smooth.Source: §5.3 · p. 13

6. THE PLANTED MODEL

This section proves Proposition 4.3 by relating the planted coloring model to bounds on the number of colorings in ordinary random graphs, using separability and a Potts-partition-function argument. It also develops a component of the proof of Lemma 6.4, establishing positive β at z = ln k + d and deriving (6.28) from Lemma 6.11.

6.2. Proof of Lemma 6.1.

  • When (2k−1) ln k−2 ≤ d ≤ (2k−1) ln k and (4.6) holds, dk,crit ≥ d; within that d range, the planted coloring σ is separable w.h.p. in G(n,p′,σ).Source: §6.1 · p. 13, §6.2 · p. 14

6.1. Overview.

  • The overview reduces Proposition 4.3 to planted-model cluster-size bounds and an exponential-moment bound, using a fixed-edge planted graph conditioned on a map being a coloring.The planting trick links exponentially rare events in the planted model to a reduced expected coloring count in the ordinary random graph.Source: §6.1 · p. 13

6.3. Proof of Lemma 6.2.

  • If the planted fixed-edge model has events that are exponentially unlikely while those events occur with high probability in G(n,m), then the expected coloring count is exponentially suppressed, implying dk,crit ≤d.Lemma 6.6 transfers the fixed-edge expectation bound to G(n,c/n) for every c>d.Source: §6.1 · p. 13, §6.3 · p. 15

6.4. Proof of Lemma 6.4.

  • A large-β Potts partition function penalizes monochromatic edges and approximates the coloring count, while concentration of its Lipschitz logarithm supports the bound obtained from balanced planted instances.The proof of Lemma 6.4 uses balanced maps and a fixed-edge-count sequence to derive an exponentially small probability that the planted partition function falls below the required level.Source: §6.1 · pp. 13–14, §6.4 · p. 17
  • For z = ln k + d, Lemma 6.7 yields β > 0.Source: §6.4 · p. 18
  • The proof aims to establish α > 0 for sufficiently large n.Source: §6.4 · p. 18
  • The bound ln Zβ,k(G(n, µn, σn)) ≤ βµn = O(n) is used with (6.26) for sufficiently large n.Source: §6.4 · p. 18
  • Lemma 6.11 implies (6.28).Source: §6.4 · p. 18

7. THE FIXED POINT PROBLEM

This section studies fixed points associated with the candidate coloring distribution, including symmetric and frozen fixed points, and establishes uniqueness properties. It also relates legal-coloring counts on decorated trees to local entropy terms and identifies a unique zero of the condensation function.

7.1. The branching process.

  • The fixed point q∗ is unique in [2/3, 1], satisfies q∗=1−1/k+o_k(1/k), and makes GW(d, k, q∗) sub-critical.Source: §7.1 · pp. 18–20

7.2. The “hard fields”.

  • Every frozen fixed point has hard-field masses ρi(π)=q∗/k, and its mass on each face agrees with that of πd,k,q∗.Source: §7.2 · pp. 22, 24

7.3. The fixed point.

  • πd,k,q∗ is the unique frozen fixed point of Fd,k when d ≥ (2k −1) ln k −2.Source: §7.3 · p. 25
  • The map from frozen fixed points of Fd,k to fixed points of the extended map is a bijection.The correspondence sends π to the family (πi,ℓ).Source: §7.3 · p. 26
  • The extended map has a unique fixed point: the candidate distribution is fixed by it, and the map has at most one fixed point.The fixed-point correspondence identifies fixed points of the extended map with frozen fixed points of the original map.Source: §7.3 · pp. 26–27

7.4. The number of legal colorings.

  • For any decorated tree with at least one legal coloring, the logarithm of its number of legal colorings equals the sum of its vertex contributions.Fact 7.17 expresses this as ln Z(T, ϑ) = Σ_v φ(T, ϑ, v).Source: §7.4 · p. 28
  • The random decorated tree has the same distribution after re-rooting at a uniformly chosen vertex.This is the unimodularity property used in the coloring-count argument.Source: §7.4 · p. 29
  • The expected local contribution on the random tree equals φd,k(πd,k,q∗).This identifies the tree expectation with the functional evaluated at the candidate fixed-point distribution.Source: §7.4 · p. 30
  • The condensation function Σk has a unique zero, denoted dk,cond.The proof combines the preceding estimates with the stated asymptotic relations.Source: §7.4 · p. 32

8. THE CLUSTER SIZE

This section develops and analyzes warning propagation as a way to estimate cluster size, relating colorings allowed by vertex lists to the cluster and studying reduced-graph components, their branching-process statistics, and large neighborhoods. It also provides technical bounds and concentration arguments, including a proof of Lemma 8.2 using Warnke’s inequality.

8.1. Preliminaries.

  • For ω = 10⌈ln ln ln n⌉, with probability 1 − exp(−Ω(ln² n)), the random graph G satisfies |∂ω G(v)| ≤ n^0.01 for every vertex v.Source: §8.1 · p. 32

8.2. Warning Propagation.

  • Warning Propagation produces color lists that match each vertex’s cluster-allowed colors for all but o(n) vertices, while a core-based initialization yields lists containing every cluster-allowed color.On tree neighborhoods, the iterated lists encode the colors a vertex can take when colors outside the neighborhood are fixed; core vertices remain frozen to their original colors.Source: §8.2 · pp. 33, 35
  • With high probability, ln Z(GWP(σ)) = ln |C(G, σ)| + o(n); the standard reduced-graph count is a lower bound and a modified count supplies an upper bound.The two counts bracket the cluster size, and the upper bound differs from the lower bound by o(n) in logarithmic scale.Source: §8.2 · pp. 33–35
  • The original initialization can falsely mark vertices as frozen in a Kempe chain, motivating a second process initialized with warnings only from core vertices to obtain an upper bound.The passage illustrates this limitation with a four-cycle whose vertices can be recolored by swapping two colors.Source: §8.2 · pp. 34–35
  • For every ε > 0, with high probability all but εn vertices lie in reduced-graph components of bounded size, and the two reduced graphs have identical components for all but o(n) vertices.The component-size bound supports comparing the counts from the two reduced graphs.Source: §8.2 · p. 36
  • Warning propagation gives L(y) = L′(y) and, for the considered tree neighborhoods, T(v) = T′(v).The component identification uses the equality of the vertex color lists and the inclusions between the corresponding neighborhoods.Source: §8.2 · p. 37

8.3. Counting legal colorings.

  • With high probability, the fraction of vertices whose rooted decorated neighborhood has type T converges in probability to its probability under the branching-process tree distribution.The distribution is that of the rooted, decorated tree generated by GW(d, k, q*).Source: §8.3 · pp. 37–38
  • For each fixed depth t, the fraction of vertices with color list {i} at depth t is approximated by the t-th iterate q_t of the fixed-point map.The iterates start from the uniform vector q_0 and are defined by q_t = F(q_{t−1}).Source: §8.3 · p. 38

8.4. Proof of Lemma 8.13.

  • The proof of Lemma 8.13 defines wobbly sets of size θ and shows that any sufficiently large T′′(v) contains a θ-vertex subtree whose vertex set is wobbly.Here θ = ⌈ln ln n⌉; the excerpt states that it suffices to bound the vertices contained in wobbly sets, but does not provide that bound.Source: §8.4 · p. 40
  • In Lemma 8.13’s proof, the W3 and W2 conditions force local events L(u, {j}) in either case considered, allowing bounds from (8.29) to be applied.When σ(u) belongs to Λ(P(u), S), that event has probability at most k^-1/2 because σ(u) is random.Source: §8.4 · p. 42
  • For vertices w in S \ U, the proof bounds the probability of the required local events by k^-0.99|S\U|, then combines this with earlier bounds and uses Cayley’s formula.The proof also bounds the probability that T is contained in G(n, p′, σ) by p′θ−1.Source: §8.4 · p. 42
Loading 1404.5513v1…