PaperlayerView exact revision on arXiv

Source-linked AI summary

Chasing the k-colorability threshold

Amin Coja-Oghlan, Dan Vilenchik

arXiv:1304.1063v3cs.DMmath.CO

TL;DR

The typical chromatic number of random graphs remains an open question, including whether the sequence of colorability thresholds converges to a uniform threshold. The paper develops a physics-enhanced second-moment argument and establishes a lower bound that pins down the chromatic number on a set of asymptotic density 1.

  • Problem

    The typical chromatic number of G(n, d/n) is an open question, including whether d_k,col(n) converges to a uniform threshold.

    Source: §1 · p. 1, §1.1 · p. 1

  • Method

    The authors develop a physics-enhanced second-moment argument whose bound matches the predicted condensation or Kauzmann transition.

    Source: §1.1 · p. 3

  • Results

    As n→∞, d_k,col(n) ≥ d_k,cond − o_k(1), where d_k,cond = 2k ln k − ln k − 2 ln 2.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The bound pins down the chromatic number precisely on a set of asymptotic density 1, giving a near-complete answer to Erdős and Rényi’s question.

    Source: §1.1 · p. 2

    The 1RSB prediction for d_k,col remains unproved, and its physics derivation takes the existence of the limiting threshold for granted.

    Source: §2.5 · p. 8

Abstract

from arXiv · show

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 $k$-SAT or $k$-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 $k$-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 $k$-colorings, allows us to establish a substantially improved lower bound on the $k$-colorability threshold. The new lower bound is within an additive $2\ln 2+o_k(1)\approx 1.39$ of a simple first-moment upper bound and within $2\ln 2-1+o_k(1)\approx 0.39$ of the physics conjecture. By comparison, the best previous lower bound left a gap of about $2+\ln k$, unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004].

1. INTRODUCTION

The paper addresses the typical chromatic number of sparse random graphs and improves rigorous bounds on the k-colorability threshold. Its physics-informed second-moment approach also determines the chromatic number on a set of average degrees of asymptotic density 1.

1. INTRODUCTION

  • The central question is the typical chromatic number of G(n, d/n); the paper notes that whether the threshold sequence converges to a uniform threshold remains open.A k-colorability phase transition is widely conjectured for each fixed k ≥ 3.Source: §1 · p. 1, §1.1 · p. 1

1.1. Background and main results.

  • Theorem 1.1 gives the rigorous lower bound dk−col ≥ 2k ln k − ln k − 2 ln 2 − o_k(1), and the paper determines the chromatic number for a set of average degrees of asymptotic density 1.For d in that set, the paper states that the probability χ(G(n, d/n)) equals the specified value tends to 1.Source: §1.1 · p. 2
  • The proof combines coloring-geometry intuition from physics with a second-moment argument and a local-variations approach to optimizing a non-convex function over the Birkhoff polytope.The authors present these as two ingredients in improving on Achlioptas and Naor.Source: §1.1 · pp. 2–3

1.2. Related work.

  • Earlier rigorous results verified physics predictions for some binary problems, but the authors identify random graph coloring as a multi-valued problem where a substantial gap remained.The paper also situates its approach alongside earlier second-moment work on coloring and related problems.Source: §1.2 · p. 3

1.3. Notation and preliminaries.

  • The analysis uses G(n,m) with m = ⌈dn/2⌉ because its edge count is fixed, and states that results transfer to G(n,d/n).The asymptotic results take n to infinity with d and k fixed, and assume k is sufficiently large where needed for Theorem 1.1.Source: §1.3 · p. 4

2. OUTLINE

The outline develops a second-moment route to lower-bounding the k-colorability threshold, then adapts it using physics-inspired constraints on coloring overlaps. It explains how this approach reaches the condensation threshold and why that threshold limits this class of second-moment arguments.

2.1. The second moment method.

  • A suitable nonnegative coloring count with controlled first and second moments gives a positive probability of k-colorability, hence a lower bound on the threshold.The outline connects the Paley-Zygmund inequality to the threshold lower bound.Source: §2.1 · p. 4

2.2. Balanced colorings and the Birkhoff polytope.

  • For balanced colorings, the second moment becomes an optimization of the overlap function f over the Birkhoff polytope, with the uniform overlap matrix as the needed maximizer.The high-dimensional overlap matrix records the shared color-class proportions; unlike binary problems, this parameter makes the optimization more difficult.Source: §2.2 · pp. 5–6

2.3. The singly-stochastic bound.

  • Achlioptas and Naor’s singly-stochastic relaxation has its maximum at the uniform matrix for d ≤ d_k,AN, but beyond that range competing matrices undermine the bound.A doubly-stochastic stable matrix also exceeds the uniform matrix’s value below the condensation threshold, so balanced colorings alone do not suffice.Source: §2.3 · p. 6

2.4. A physics-enhanced random variable.

  • The paper counts tame rather than all balanced colorings, preserving an exponentially large first moment while restricting overlaps so the second-moment bound holds up to d_k,cond − o_k(1).The restriction excludes wild colorings that can inflate the second moment; a local-variations argument handles the resulting optimization over a reduced domain.Source: §2.4 · pp. 6–7

2.5. The condensation phase transition.

  • The condensation transition explains the second-moment barrier: above it, colorings can be correlated within large clusters, and the paper’s approach is best possible in its stated sense.The authors also report that the 1RSB prediction for the threshold remains unproved and is not explicit, involving a difficult fixed-point problem.Source: §2.5 · p. 8

3. THE FIRST MOMENT

Under the planted model, the proof controls coloring clusters by identifying a large core and bounding the number of vertices that can vary within a cluster. At d=d_k,cond−ε_k, this yields a high-probability bound on cluster size by the expected number of balanced colorings.

Core construction

  • The core is the largest vertex set in which every vertex has at least 100 neighbors of each other color within the set.The proof uses this core to constrain recolorings within C(σ).Source: §3 · pp. 8–9

Cluster-size bound

  • Vertices outside the core that are not σ-complete have restricted recoloring choices, and most miss exactly one other color.For vertices in F1\F2, all colorings in C(σ) assign a color from a set of at most two colors.Source: §3 · pp. 9–10

Expansion properties

  • Lemma 3.2 bounds the number of 1-free vertices by n/k(1+Õ_k(1/k)) and the number of 2-free vertices by Õ_k(k^-2)n.It also supplies expansion properties P1–P3 used in the proof.Source: §3 · p. 9

Separation

  • With high probability, σ is separable in G(n,m,σ), so another coloring with sufficient overlap must have overlap above 1−κ.The proof assumes an overlap of at least 0.51 and aims to show it exceeds 1−κ.Source: §3 · p. 9

Fixed vertices

  • With high probability, every σ-complete vertex keeps its color in every coloring in C(σ).A σ-complete vertex has a core neighbor of each color other than its own.Source: §3 · pp. 9–10

Lemma 3.1

  • At d=d_k,cond−ε_k, |C(σ)|≤E[Z_k,bal] w.h.p., establishing the cluster-size bound T3.The proof takes ε_k=Θ_k(k^-1/2).Source: §3 · p. 10
  • At this density, k·f(ρ̄)=2 ln 2+o_k(1)>0.The proof obtains this value at d=2k ln k−ln k−2 ln 2−ε_k.Source: §3 · pp. 8, 10

4. THE SECOND MOMENT

This section analyzes the second-moment objective over tame overlap matrices, reducing candidate maximizers and bounding the objective across several matrix classes. It establishes the barycentre as the strict maximizer in the tame domain through stability, local variations, and entropy and energy comparisons.

4.1. Overview.

  • If f is uniquely maximized at the barycentre over tame overlaps, Proposition 4.1 bounds E[Z2 k,tame] by O(E[Zk,tame]2); Proposition 4.2 establishes this across stable-overlap ranges.The ranges are 1 ≤ s ≤ k^0.999, k^0.999 < s < k − k^0.49, and k − k^0.49 ≤ s < k; the s = 0 case follows separately from Corollary 4.8.Source: §4.1 · pp. 11–12

4.3. Proof of Proposition 4.7.

  • For a row and column set J with |J| ≥ k^λ and max_j∈J ρ_ij < λ/2 − ln ln k/ln k, equalizing that row’s mass on J does not decrease f and strictly increases it unless unchanged.The condition requires 3 ln ln k/ln k ≤ λ ≤ 1.Source: §4.1 · p. 12

4.2. Preliminaries.

  • The preliminaries bound entropy by the logarithm of support size and calculate f at the barycentres of faces defined by fixed diagonal entries.For a probability distribution supported on s elements, H(p) ≤ ln s; the face-centre calculation uses rows with entropy 0 or ln(k − s).Source: §4.2 · pp. 12–13

4.4. Proof of Proposition 4.3.

  • An entry in [0.49, 0.51] permits a change to ρ′ with f(ρ′) ≥ f(ρ) + ln k, while any singly-stochastic matrix with an entry in [0.15, 0.51] has f(ρ) < 0.The first bound rules out a maximum near one-half; the second is Proposition 4.3.Source: §4.1 · p. 11, §4.4 · p. 15
  • Matrices with an entry in [0.49, 0.51], or a row maximum in [0.15, 0.49], satisfy f(ρ) < 0.For the row-maximum case, the proof uses ρ11(1 − ρ11) > 1/8 throughout the interval.Source: §4.4 · pp. 18–19

4.5. Proof of Proposition 4.4.

  • For 1 ≤ s ≤ k^0.999, the maximizer over D_s,tame satisfies f(ρ) < f(ρ̄) − 1/k + o_k(1/k).The comparison bounds the entropy and energy of a simplified matrix by those of the s-stable barycentre, up to o_k(1/k).Source: §4.5 · pp. 19–20

4.6. Proof of Proposition 4.5.

  • The cited claims give two results for ρ̂: the entropy obeys H(ρ̂) ≤ 2 ln k + 3q(2 + ln k), and the energy is exactly E(ρ̂) = −2 ln k + s ln k.Source: §4.6 · pp. 21–22
  • For Proposition 4.5, the maximizer ρ over D_s,tame satisfies f(ρ) < 0 < f(ρ̄).The proof uses an upper bound on f(ρ) to establish the negative value.Source: §4.6 · p. 23

4.7. Proof of Proposition 4.6.

  • Claim 4.22 bounds E(ρ) by E(id) + (1 + Õ_k(1/k)) ln k.This energy comparison is used in the proof of Proposition 4.6.Source: §4.7 · p. 24
  • For Proposition 4.6, f(id) < f(ρ̄), with f(ρ̄) > 0.The proof compares f(id) with the value at the reference matrix ρ̄.Source: §4.7 · p. 25

5. THE LAPLACE METHOD

The section bounds the second-moment contribution by partitioning overlap matrices into regions around the balanced overlap and controlling each region. Near the balanced overlap, a negative-definite Hessian gives local control; farther away, separate arguments handle stable and other overlaps.

5. THE LAPLACE METHOD

  • For every overlap matrix ρ, E[Zρ,tame] ≤ E[Zρ,bal] ≤ O(n^((1−k^2)/2)) · exp(n · f(ρ)), uniformly in ρ.This bound is the starting point for estimating the second-moment sum.Source: §5 · p. 25
  • At the balanced overlap ˜ρ, the first derivative of f ◦ L vanishes and its Hessian is negative definite, yielding uniform local curvature around that point.The largest eigenvalue remains bounded below zero in a neighborhood independent of n, so Taylor expansion controls overlaps near the balanced matrix.Source: §5 · pp. 25–26
  • The section completes the proof of Proposition 4.1 by combining the local estimate with the bounds for the other overlap regions.The stated conclusion follows from (5.8) and Lemmas 5.1, 5.2, and 5.4.Source: §5 · pp. 26–27
  • For overlaps in R2, the total tame-coloring pair contribution is at most C times E[Zk,tame]^2, for C depending on k.Overlaps with entries above 0.51 can be aligned by a color permutation and related to the cluster C(σ).Source: §5 · pp. 25–26
  • Every overlap matrix is within C/√n of a doubly-stochastic matrix, for C depending on k.The proof adjusts row sums and then column sums to obtain the nearby matrix.Source: §5 · pp. 26–27
  • If f(ρ) < f(¯ρ) for every other ρ in Dtame, then the R3 contribution is at most E[Zk,tame]^2.The proof uses a strict gap below f(¯ρ) away from the balanced overlap and bounds the resulting contribution exponentially.Source: §5 · p. 27

APPENDIX A. PROOF OF LEMMA 3.2

The appendix relates a planted random graph with independent cross-color edges to the fixed-edge planted model. Conditioning on the edge count gives the fixed-edge distribution, enabling probability estimates to transfer between the models.

APPENDIX A. PROOF OF LEMMA 3.2

  • The section works under 2k ln k − ln k − 2 ≤ d ≤ 2k ln k and uses a binomial tail bound for estimates.The stated Chernoff bound controls upper and lower deviations from the mean, with a simpler upper-tail form for t > 1.Source: Appendix A · pp. 28–29
  • Conditioned on having m edges, G(n,p,σ) has the same distribution as G(n,m,σ).The choice of p makes the expected edge count m, and the probability of exactly m edges is at least (C√n)^−1 for C depending on k.Source: Appendix A · p. 28
  • Properties P1–P4 holding in G(n,p,σ) with probability 1−O(1/n) implies they hold w.h.p. in G(n,m,σ).Fact A.1 provides the model comparison used for this transfer.Source: Appendix A · pp. 28–29

A.1. Proof of P1.

The proof of P1 bounds the chance that a subset of one color class has too many vertices outside it with no neighbor in the subset. It combines a binomial tail estimate with a union bound over subsets.

A.1. Proof of P1.

  • For a subset S ⊂ V1 of size αn/k, the number of vertices outside V1 with no neighbor in S is binomial, with mean bounded using the assumed range of α and d.The proof considers 0.509 ≤ α ≤ 1 − k^−0.499 and derives (1−p)αn/k ≤ 2k^−2α.Source: §A.1 · p. 29
  • A union bound over subsets S reduces the proof to showing its right-hand side is exp(−Ω(n)).The subset count is compared with the tail estimate for the number of outside vertices lacking neighbors in S.Source: §A.1 · p. 29
  • The inequality needed for that bound holds throughout 0.509 < α < 1 − k^−0.499, as verified at both endpoints and by convexity.The exponential and linear sides intersect at most twice, and the linear side is larger between the intersections.Source: §A.1 · p. 29

A.2. Proof of P2.

The proof estimates how many vertices outside a color class have fewer than 15 neighbors in it, using binomial and Chernoff bounds.

A.2. Proof of P2.

  • For v outside Vi, its neighbor count in Vi has mean λ = |Vi|p ∼ np/k > 2 ln k, and the probability of fewer than 15 neighbors is at most 2k^−2 ln^14 k.The total number Yi of such vertices has mean at most 3k^−2 ln^14 k; the proof then applies a Chernoff bound with κ = k^−1 ln^20 k.Source: §A.2 · p. 30

A.3. Proof of P3.

The proof bounds the probability of violating P3 by estimating the number of sets whose induced edge count is at least five times their size. For each pair of vertices in S, the edge probability is at most p.

A.3. Proof of P3.

  • For any two vertices in S, their connection probability is at most p, so e(S) is stochastically dominated by a binomial random variable.Source: §A.3 · p. 30
  • Xα counts sets S of size αn whose induced edge count is at least 5|S|.Source: §A.3 · p. 30
  • The probability that any set violates P3 is O(1/n).Source: §A.3 · p. 30

A.4. Proof of P4.

The proof constructs a large core by removing vertices through an iterative process, then bounds the exceptional sets and their neighborhoods. These bounds support estimates on the numbers of 1-free and 2-free vertices.

A.4. Proof of P4.

  • With probability 1 − exp(−Ω(n)), the core contains (1 − ˜O_k(k^-1))n vertices.Source: §A.4 · p. 30
  • The core construction iteratively removes vertices with too few neighbors of some other color, using sets W, U, and Z.CR1 defines W from vertices with fewer than 300 neighbors in another color class; CR2 and CR3 define U and iteratively build Z.Source: §A.4 · p. 30
  • With probability at least 1 − exp(−Ω(n)), |U| ≤ n/k^30 and |Z| ≤ n/k^29.Source: §A.4 · p. 31
  • With probability 1 − exp(−Ω(n)), every Y of size at most nk^-29 has at most nk^-20 vertices in its neighborhood.Source: §A.4 · pp. 31–32
  • Every 1-free vertex lies in S0, S1, Z, or N(Z), and |S1| is at most ˜O_k(k^-2)n with probability 1 − exp(−Ω(n)).Source: §A.4 · p. 32
  • With probability at least 1 − exp(−Ω(n)), at most n ˜O_k(k^-5) vertices have at most 100 neighbors in each of two distinct color classes.The 2-free vertices are contained in S2 ∪ Z ∪ N(Z).Source: §A.4 · p. 33
Loading 1304.1063v3…