PaperlayerView exact revision on arXiv

Source-linked AI summary

Phase Transitions in the Coloring of Random Graphs

Lenka Zdeborová, Florent Krzakala

arXiv:0704.1269v2cond-mat.dis-nncond-mat.stat-mechcs.CC

TL;DR

The paper asks how proper colorings of sparse random graphs are organized and when coloring becomes computationally difficult. It applies cavity analysis with one-step replica symmetry breaking to characterize solution-space transitions. The results distinguish clustering from hardness and suggest freezing as the relevant phenomenon.

  • Problem

    Sparse random-graph coloring has a sharp coloring threshold and becomes harder near that threshold, but the structural transition responsible for this hardness is unclear.

  • Method

    The paper uses the cavity method, including one-step replica symmetry breaking, to analyze clusters, frozen variables, and algorithms for random-graph colorings.

  • Results

    As connectivity increases, solutions undergo clustering, condensation, freezing, and eventual disappearance above the coloring threshold.

  • Takeaways & Limitations

    Clustering itself is not associated with the onset of computational hardness; the paper instead suggests rigidity/freezing as the relevant phenomenon.

Abstract

from arXiv · show

We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs and determine their asymptotic values for large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.

I. INTRODUCTION

Graph coloring asks whether vertices can receive q colors without equal colors on adjacent vertices, a problem that is hard on general graphs and exhibits a sharp threshold on sparse random graphs. The paper uses the cavity method to characterize successive structural transitions in the solution space and their algorithmic implications.

  • Motivation: Graph coloring assigns q colors to vertices so adjacent vertices receive different colors.The problem has applications including timetabling, scheduling, compiler register allocation, and mobile-radio frequency assignment.
  • Random-graph threshold: For sparse random graphs, proper colorings exist with high probability below c_s and fail with high probability above it.Here c denotes average vertex connectivity.
  • Phase transitions: The solution space changes from one cluster to exponentially many clusters at the dynamic/clustering transition c_d.The coloring threshold c_s occurs later, above which no solutions exist.
  • Phase transitions: At the condensation transition c_c, the measure concentrates on the largest clusters, while the total entropy becomes smaller than the annealed value.Before condensation, the measure is dominated by exponentially many clusters and the annealed entropy remains correct.
  • Phase transitions: At the rigidity/freezing transition c_r, dominant clusters acquire a finite fraction of frozen variables.A frozen variable has the same color in every solution within its cluster.
  • Approach and implications: The paper applies one-step replica symmetry breaking to compute the critical connectivities for Erdős-Rényi and regular random graphs.It also discusses consequences for uniform sampling, Walk-COL, and belief propagation.

III. THE CAVITY FORMALISM AT THE REPLICA SYMMETRIC LEVEL

The replica-symmetric cavity method represents coloring marginals through recursively updated cavity probabilities on locally tree-like structures. It is exact on trees under suitable independence conditions and supplies free-energy, energy, entropy, and marginal calculations for the random-graph analysis.

  • III. THE CAVITY FORMALISM AT THE REPLICA SYMMETRIC LEVEL: The RS cavity formalism begins by reviewing when the replica-symmetric approach applies and where it fails.Its central assumption is that neighboring cavity probabilities factorize when the node is removed.
  • A. The replica symmetric cavity equations: Belief propagation solves coloring on a tree through iterative updates of cavity probabilities and computes node marginals.Boundary conditions are required because an unconstrained tree is always 2-colorable.
  • A. The replica symmetric cavity equations: The cavity recursion combines incoming neighbor messages while excluding the target edge.The associated normalization is a cavity partition sum and tracks the free-energy shift from adding a node and surrounding edges.
  • A. The replica symmetric cavity equations: Adding all incident edges yields the node marginal normalization, while adding an edge gives a separate free-energy shift.These shifts are assembled into the thermodynamic free-energy density.
  • A. The replica symmetric cavity equations: The free-energy relation is variational, and energy and entropy densities follow through a Legendre transform.The intensive variables include f = F/N, e = E/B, and s = S/N.
  • A. The replica symmetric cavity equations: Cavity probabilities and cavity fields are related representations suited to different zero-temperature limits.The probability representation yields zero-temperature belief propagation, whereas the field representation yields Warning Propagation and neglects entropic contributions.

B. Average over the ensemble of graphs and the RS solution

The ensemble-averaged RS analysis solves a self-consistent distributional cavity equation for sparse random-graph degree ensembles. It identifies the paramagnetic solution, its stability limits, and the assumptions governing RS validity.

  • B. Average over the ensemble of graphs and the RS solution: Quenched observables are obtained by solving a self-consistent cavity functional equation determined by the degree distribution.Population dynamics provides a numerical solution because the order parameter is a nontrivial distribution.
  • B. Average over the ensemble of graphs and the RS solution: The analysis restricts P(ψ) to color-symmetric functions, which can omit color-asymmetric solutions in some ensembles.The authors argue this restriction is justified for the random-graph ensembles studied.
  • B. Average over the ensemble of graphs and the RS solution: For regular graphs, local edge equivalence makes the cavity solution factorize so every edge has the same order parameter.Bi-regular graphs similarly factorize across their two node classes.
  • B. Average over the ensemble of graphs and the RS solution: The uniform paramagnetic message P(ψ) = δ(ψ − 1/q) is always an RS solution and is the only factorized solution found in the colorable phase of regular random graphs.The RS entropy density is then straightforward to compute.
  • B. Average over the ensemble of graphs and the RS solution: The RS entropy coincides with the annealed entropy and remains valid beyond the RS phase until condensation.This extends the range in which the annealed expression correctly gives the number of solutions.
  • B. Average over the ensemble of graphs and the RS solution: The RS assumption requires sufficient independence among neighboring cavity probabilities, which loops or correlated boundaries can violate.Rigorous correctness proofs for random graphs remain largely unresolved.
  • B. Average over the ensemble of graphs and the RS solution: For regular and Erdős-Rényi graphs, the RS instability is colorable only for q = 3; for q ≥ 4, the local stability point lies beyond available coloring-threshold upper bounds.The q = 3 thresholds are c_RS^reg(3) = 5 and c_RS^ER(3) = 4, while the ER coloring threshold is approximately 4.69.

IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK

The one-step replica symmetry breaking framework restores an extremal description by decomposing the non-extremal Gibbs measure into clusters and weighting their belief-propagation fixed points. Its complexity and replicated free energy quantify how clusters contribute across free-energy densities.

  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: 1RSB decomposes a non-extremal Gibbs measure into pure states or clusters in which the measure becomes extremal.The states are represented by belief-propagation fixed points.
  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: The number of pure states can grow exponentially with system size, described by the complexity Σ(f).Σ(f) is the logarithmic density of states with internal free-energy density f.
  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: Each state is weighted by its free energy raised to the Parisi parameter m, analogous to inverse-temperature weighting.This reweighting determines the statistical treatment of BP fixed points.
  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: The 1RSB distribution P_i→j(ψ_i→j) is constructed from incoming field distributions and a delta constraint enforcing BP fixed points.The reweighting term accounts for the free-energy change after adding a cavity spin and adjacent edges.
  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: Population dynamics numerically represents P(ψ) by a finite set of sampled cavity fields.Uniform sampling from that set approximates the probability measure P(ψ)dψ.
  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: The replicated free energy Φ(β,m) is related to the complexity through a Legendre transform.The transform yields Σ, f, and the conjugate relation βm = ∂fΣ(f).
  • IV. ONE-STEP REPLICA SYMMETRY BREAKING FRAMEWORK: At m = 1, the replicated free energy reduces to the usual RS free-energy function.The decomposition uses cluster internal entropy s and total entropy density s_tot.

A. Analyzing the 1RSB equations

The 1RSB framework decomposes the coloring solution space into clusters and distinguishes clustered, condensed, and zero-temperature regimes. The entropic limit focuses on zero-energy proper colorings, whose cluster-size distribution and frozen variables characterize the solution space.

  • Phase structure: At m = 1, positive complexity signals an exponential number of thermodynamically dominating clusters, whereas negative complexity yields condensation onto states with Σ(m∗) = 0.The clustered phase has exponentially many dominating states; in the condensed phase, the total entropy is dominated by a smaller set of states.
  • Phase structure: The clustering transition is a dynamical transition rather than a thermodynamic singularity because the total free energy remains equal to the replica-symmetric value at m∗ = 1.The condensation transition is instead a genuine thermodynamic transition with a discontinuity in the second derivative of the free energy.
  • Method: The 1RSB results are obtained through a one-step replica-symmetry-breaking cavity solution, with population dynamics used for numerical evaluation over random-graph ensembles.For random regular graphs, a factorized functional solution simplifies the numerical calculation; m = 1 also permits a simpler reconstruction-based formulation.
  • Survey propagation: Survey propagation derives from the energetic zero-temperature formalism, but that formalism cannot determine cluster-size weighting and is therefore unsuitable for locating the clustering transition.The entropic analysis distinguishes numerous small clusters from fewer larger clusters, which energetic weighting treats equally.
  • Zero-temperature limit: The entropic zero-temperature limit fixes the energy to zero, so the partition sum counts proper colorings and clusters are weighted by their size to the power m.The resulting free entropy encodes the complexity Σ(s), the log-number of clusters of a given size.
  • Frozen variables: Hard fields allow only one color and therefore identify frozen variables, while soft fields leave multiple colors allowed within a cluster.A finite fraction of variables can be frozen inside a single cluster even though such a fraction cannot occur across the entire colorable solution space.

1. Hard fields in the simplest case, m = 0

At m = 0, the survey-propagation equations count clusters without weighting them by size. This exposes limitations of the energetic formalism and motivates generalized recursions that incorporate hard- and soft-field reweighting.

  • m = 0: At m = 0, a nontrivial solution counts the total log-number of clusters because Σ(s) has zero slope and clusters are weighted equally by size.The value Σ(s)|m=0 is the maximum of the complexity curve when the nontrivial solution exists.
  • m = 0: The energetic formalism cannot determine whether exponentially many clusters are small or whether fewer larger clusters dominate the solution space.This limitation arises because energetic calculations weight clusters equally independently of their size.
  • m = 0: A nontrivial solution may be absent even when many clusters exist, if the complexity curve has no zero-slope segment.Thus, failure to find the nontrivial m = 0 solution does not establish that clusters are absent.
  • m = 0: The energetic method can locate the coloring threshold and derive survey propagation, but it is not a reliable tool for studying the clustering transition.The paper reports that both cases—nontrivial and absent m = 0 solutions—occur.
  • Generalized recursion: Generalized survey propagation updates the hard-field fraction and then reweights fields, requiring the ratio r between soft- and hard-field reweightings.Computing r generally depends on the full soft-field distribution, making the recursion difficult to close.
  • Generalized recursion: The generalized recursion simplifies at m = 0, recovering original survey propagation, and at m = 1, where reconstruction yields closed equations.The generalized equation remains potentially useful for algorithms, although using an edge-independent approximation for r is suggested only as an approximation.

3. The presence of frozen variables

Hard fields mark frozen variables within solution clusters, and their emergence is analyzed through the 1RSB equations. As connectivity increases, solution space passes from replica-symmetric behavior through clustering and condensation to rigidity and eventual uncolorability.

  • Mechanism: q −1 incoming fields are required to constrain a node to one color, so hard fields can arise only when sufficiently many neighboring fields forbid alternatives.The update function is zero below q −1 incoming fields.
  • Onset of hard fields: An extensive q-core is necessary and sufficient for the first nontrivial hard-field solution in the r →0 limit.For regular graphs this occurs at connectivity c = q; for Erdős-Rényi graphs, c3 = 3.35, c4 = 5.14, and c5 = 6.81.
  • Solution branches: For regular graphs, the hard-field solution exists over [−∞, mr], while the soft-field solution exists over [ms, ∞]; increasing connectivity narrows the gap between these intervals.At rcrit, the hard-field solution disappears discontinuously, leaving only η = 0; no frozen-variable solution exists for m > mr.
  • Clustering: At the clustering threshold, exponentially many clusters replace the single large replica-symmetric cluster, although the RS entropy and marginals remain correct while complexity at m = 1 is non-negative.For 6-coloring on regular graphs, clustering occurs at c = 18.
  • Condensation and uncolorability: At condensation, complexity at m = 1 becomes negative and entropy is dominated by clusters with m* < 1; at the coloring threshold, proper colorings disappear.For 6-coloring, condensation occurs at c = 19 and uncolorability at c = 20.
  • Rigidity: The rigidity transition occurs when dominant clusters contain a finite fraction of frozen variables; for regular 6-coloring, cr = 19.Within such a cluster, those variables take one color in every solution belonging to that cluster.

B. Results for the bi-regular ensemble

The bi-regular analysis reveals distinct structural regimes, including condensation before rigidity in one ensemble and coincident clustering and condensation in another. These results parallel the Erdős-Rényi phenomenology while exposing a special continuous-transition case for 3-coloring.

  • Bi-regular methodology: The bi-regular ensemble fine-tunes connectivity while preserving 1RSB factorization, improving numerical precision.Messages in opposite directions are uniform, yielding a bifactorized solution.
  • Bi-regular methodology: 4-coloring of 5-21-bi-regular graphs is already condensed beyond clustering, with entropy dominated by soft-field clusters.The complexity curve retains a gap between hard-field and soft-field solutions.
  • Bi-regular transition structure: 28 is the coincident clustering and condensation connectivity for 4-coloring of 4-c-bi-regular graphs; survey propagation begins at 37, rigidity occurs at 49, and coloring ends at 57.The replica-symmetric solution is unstable above c=28, while the later transitions remain distinct.
  • Bi-regular transition structure: For 4-c-bi-regular graphs, an unphysical soft-field branch persists even after the hard-soft gap closes.For c≤42 the gap exists, and below m_r two solutions can depend on whether the initial population contains enough hard fields.
  • Erdős-Rényi comparison: In Erdős-Rényi graphs with q>3, clustering creates exponentially many clusters, condensation removes their complexity, and the coloring threshold discontinuously eliminates all clusters.At condensation, total entropy becomes non-analytic and falls below the replica-symmetric value.
  • Overlap structure: Overlap analysis distinguishes intra-cluster similarity from overlaps between color-permuted clusters, parameterized by the number of fixed positions in the permutation.The distribution of overlaps is computed using a Poisson-Dirichlet process and is not self-averaging.

D. Large q Asymptotics

The large-q analysis derives asymptotic locations for rigidity, condensation, and coloring transitions and shows that near the coloring threshold connectivity mainly removes clusters rather than shrinking them. The paper then connects these structural results to algorithmic behavior, arguing that rigidity, not clustering, marks the relevant hardness regime.

  • Asymptotic transitions: The regular and Erdős-Rényi ensembles have equivalent large-q asymptotics to the stated orders.Corrections are smaller than the orders retained in the expansion.
  • Asymptotic transitions: c_SP=q[log q+log log q+1−log 2+o(1)] and c_r=q[log q+log log q+1+o(1)] locate survey propagation and rigidity transitions.The clustering transition satisfies c_d<c_r, and finite-q cases place c_d between c_SP and c_r.
  • Asymptotic transitions: c_c=2q log q−log q−2 log 2+o(1), while c_s=2q log q−log q−1+o(1).Condensation is therefore close to the coloring threshold but far from clustering and rigidity at large q.
  • Large-q structure: The replica-symmetric entropy correctly gives the number of solutions below condensation.The paper states that the RS free energy remains correct until c_c.
  • Large-q structure: Near the coloring threshold, connectivity changes the number of clusters rather than their internal entropy.Clusters are dominated by frozen variables, so adding a link usually destroys a cluster instead of making it smaller.
  • Algorithmic consequences: The paper argues that clustering does not mark algorithmic hardness, whereas rigidity may be relevant because known algorithms tend to find solutions with trivial whitening.Beyond rigidity, clusters without hard fields become rare, although the q≥9 case retains a stated possibility of soft clusters.
  • Algorithmic consequences: Whitening uses warning propagation to distinguish clusters containing frozen variables from clusters without them.Iterative updates from a solution yield all-white edges for a non-frozen cluster and non-white edges for a frozen cluster.
  • Algorithmic consequences: Walk-COL finds solutions in linear time in the replica-symmetric phase and can sometimes do so even beyond clustering.The method is a nonequilibrium local search strategy that does not satisfy detailed balance.

C. A belief propagation algorithm to color random graph

The paper evaluates belief propagation with decimation and places its performance within the sequence of structural transitions in random-graph colorings. It finds that clustering does not mark algorithmic failure, while rigidity may better indicate computational hardness.

  • Algorithmic consequences: Belief propagation gives correct solution counts and marginals until the condensation transition.At m = 1, the 1RSB and replica-symmetric descriptions agree for these quantities.
  • Algorithmic consequences: BP convergence fails at c = 4 for 3-coloring and after decimation for 4-coloring when a finite fraction of variables is fixed.The authors avoid this issue experimentally by fixing the iteration count rather than requiring convergence.
  • Algorithmic consequences: BP with decimation numerically finds coloring solutions, including beyond the condensation transition.The procedure iterates BP, fixes the most biased variable to its most probable color, and repeats.
  • Transition structure: At cd, the giant cluster splits into exponentially many clusters, making uniform solution sampling hard while preserving replica-symmetric entropy and marginals for cd < c < cc.The paper distinguishes this sampling difficulty from the ability to find a solution.
  • Transition structure: At cc, solutions condense onto finitely many largest clusters, and total entropy becomes smaller than the replica-symmetric entropy.The transition has a discontinuity in the second derivative of the free energy.
  • Transition structure: At cr, thermodynamically relevant clusters acquire a finite fraction of frozen variables, a transition the authors associate with the onset of computational hardness.For 3-coloring, the reported rigidity threshold is cr = 4.66, near the performance of survey propagation with decimation.

APPENDIX A: STABILITY OF THE PARAMAGNETIC SOLUTION

The appendix derives stability criteria for the replica-symmetric paramagnetic cavity solution by analyzing perturbation propagation and the associated eigenvalues. It distinguishes genuine graph instabilities from modulation effects that arise on trees but not as solutions on random graphs.

  • Stability analysis: The correlation series converges only when λ < 1, linking paramagnetic stability to a finite spin-glass susceptibility.The derivation uses the growth of nodes at distance d and the chain of infinitesimal influences along paths.
  • Stability analysis: The stability parameter is obtained from the Jacobian of the cavity recursion evaluated at the replica-symmetric paramagnetic solution.The Jacobian has two eigenvalues, corresponding to homogeneous and color-symmetry-breaking fluctuations.
  • Stability analysis: Color-symmetry-breaking fluctuations are the critical eigenmodes, whereas the homogeneous mode is not the relevant instability.The first eigenvalue is (q − 1)-fold degenerate and spans pairwise color-difference directions.
  • Critical connectivities: The critical connectivities are obtained at zero temperature for regular and Erdős-Rényi graphs.The appendix states the resulting expressions after evaluating the stability condition.
  • Modulation instability: For c > cmod, modulation instability can occur on trees, but frustrating loops prevent the corresponding antiferromagnetic solution on random graphs.The cavity fields instead oscillate between different solutions during iteration.

APPENDIX B: THE RELATIVE SIZES OF CLUSTERS IN THE CONDENSED PHASE

The appendix models relative cluster sizes in the condensed phase with a Poisson-Dirichlet process and connects its parameter to the zero-complexity point. It also simplifies the m = 1 computation of free entropy and hard-field fractions.

  • Cluster-size statistics: The Poisson-Dirichlet process represents normalized cluster sizes xi ordered from largest to smallest, with their sum equal to one.The construction uses a Poisson process with intensity proportional to y^(-1-m∗).
  • Cluster-size statistics: At Σ(m∗) = 0, xi is the fraction of all solutions contained in cluster i.The corresponding yi values are proportional to the number of solutions in each cluster.
  • Cluster-size statistics: The expected ratio of consecutive cluster sizes is E[Ri] = im∗/(1 + im∗), and the ratios are mutually independent.These relations generate the cluster-size curves shown in Figure 12.
  • m = 1 simplification: The m = 1 replicated free energy equals the replica-symmetric free energy, so total entropy at m = 1 equals the replica-symmetric entropy.This identity underlies the agreement between 1RSB and replica-symmetric solution counts before condensation.
  • Population dynamics: The population-dynamics solution is nontrivial exactly when iteration from suitable initial conditions converges to a nontrivial solution.When the paramagnetic solution is found, the appendix states that no other solutions exist.
  • Hard fields: At m = 1, the hard-field fraction follows a simplified iterative equation and becomes positive only above cr(m = 1).The computation is efficient for both regular and Erdős-Rényi graphs.

APPENDIX D: NUMERICAL METHODS

The numerical appendix explains population-dynamics procedures for solving the 1RSB equations and handling hard and soft cavity fields. It emphasizes computational simplifications, numerical ambiguity from quasi-hard fields, and validation against analytical results.

  • Population dynamics: Population dynamics represents each field distribution by a population of vectors and updates fields using the 1RSB recursion.The update first computes new vectors through the RS recursion and then applies reweighting.
  • Population dynamics: Sampling weighted fields by cumulative distributions costs O(N log N) per complete iteration, while cloning and erasing can reduce the implementation to linear time.The authors choose the faster cloning strategy despite some loss of precision from population redundancy.
  • Hard and soft fields: Quasi-hard fields with values 1 − ǫ can be numerically indistinguishable from true hard fields, even for ǫ = 10^-20.Figure 14 compares the analytical hard-field fraction with a population-dynamics estimate to expose this discrepancy.
  • Hard and soft fields: Separating hard and soft fields reduces the population size and efficiently computes hard-field fractions through generalized survey-propagation equations.Directly generating rare soft fields with uniform weight further accelerates sampling.
  • Validation: The mixed hard/soft implementation recovers the exact m = 0 energetic result and therefore provides the most precise numerical evaluation available within this approach.The free entropy is fitted and Legendre-transformed to obtain entropy and complexity.
  • Validation: Figure 15 compares fitted and analytical free entropy for 6-coloring of 19-regular graphs and 4-coloring of 9-regular graphs, alongside complexity versus internal entropy.The right panels include numerical points, the Legendre transform of the fit, and analytical Σmax.

APPENDIX E: HIGH-q ASYMPTOTICS

In the large-q limit, the regular and Erdős–Rényi ensembles share the same quenched averages, allowing the analysis to focus on regular graphs. The appendix gives the asymptotic onset of the nontrivial 1RSB solution and situates it relative to the coloring threshold.

  • The large-q quenched averages coincide for regular and Erdős–Rényi graphs, so the analysis considers the regular ensemble with connectivity c = k + 1.
  • The appendix separately identifies the coloring threshold after introducing the m = 0 solution threshold.

1. The appearance of hard fields at m = 1

The large-q analysis determines when hard fields first appear in the 1RSB solution at m = 1. This occurs at connectivity q[log q + log log q + 1 + o(1)], only beyond α = 1 in the relevant scaling.

  • The relevant scaling writes k = (q − 1)[log(q − 1) + log log(q − 1) + α] while the hard-field fraction approaches one.The fraction of soft fields is θ(q, k) = o(1).
  • α > 1 is required for a solution of the hard-field equation, because its left-hand side has maximum 1/e at γ(α) = 1.
  • cr(m = 1) = q[log q + log log q + 1 + o(1)] is the connectivity where hard fields first appear at m = 1.
  • cSP and cr(m = 1) differ only at third order and remain far from both the coloring and condensation thresholds in the large-q comparison.

2. The condensation transition

The condensation analysis expands the replicated free energy in the regime c = 2q log q − γ log q + α, accounting for hard- and soft-field reweighting. It derives the complexity and the large-q locations of the coloring and condensation thresholds.

  • The condensation transition is analyzed using the scaling cs = 2q log q − γ log q + α.
  • The soft-field reweighting is almost surely 2, yielding B = 2m/2 independently of γ and α.
  • The free-energy expansion separates site contributions according to hard, soft, and contradictory total fields, with contradictory fields having zero normalization.
  • Link contributions are computed from three cases: two hard fields, two soft fields, and one hard plus one soft field.
  • The complexity is defined as Σ = Φs(m) − ms(m), and its zero occurs at cΣ=0 = 2q log q − log q − 2 + 2m[1 − m log 2] + o(1).
  • cΣ=0(m = 0) = 2q log q − log q − 1 + o(1), while cΣ=0(m = 1) = 2q log q − log q − 2 log 2 + o(1).
Loading 0704.1269v2…