PaperlayerView exact revision on arXiv

Source-linked AI summary

Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion

Emile Anand

arXiv:2610.01071v1cs.DScs.CCcs.DMmath.CO

TL;DR

For promised 3-colorable graphs, the paper develops a root-conditioned Gaussian-cover recursion with a variance bound for Gaussian maxima. It proves a randomized polynomial-time O(n^4/23)-coloring guarantee, improving on recent bounds.

  • Problem

    The question is how many colors suffice in polynomial time for an n-vertex graph promised 3-colorable, when its three independent sets are not provided.

    Source: §1 · p. 2

  • Method

    The proof combines a fixed-depth root-correlation shell recursion on Gaussian covers with a variance bound for Gaussian maxima and finite verification of the recursion.

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

  • Results

    O(n^4/23) colors suffice in randomized polynomial time for every promised 3-colorable n-vertex graph, improving on the bounds of Bansal, Huang, and Lee and Narang and Tang.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The sparse-case guarantee combines with the dense progress bound, and the recursion requires only a constant number of neighborhood extensions while rounding full root-correlation shells.

    Source: §4 · p. 19

    The dense case is governed by a minimum-degree condition; whether expansion-type structure can substitute for or refine that condition remains open.

    Source: §3.4 · p. 19

Abstract

from arXiv · show

We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\smash{O(n^{4/23}) = O(n^{0.17391\ldots})}$ colors, improving on the recent bounds of $O(n^{0.19539})$ by Bansal, Huang, and Lee and Narang and Tang who obtained $O(n^{(13-\sqrt{97})/18+\epsilon})=O(n^{0.17506\dots + \epsilon})$ colors for every fixed $\smash{\epsilon>0}$. To prove our result, we start from a fixed-level semidefinite relaxation, where we use a finite-depth recursion on Gaussian covers. Fixing a root vertex, we group vertices by correlation with the root vector. Here, each step extends a cover of directions by one edge and transfers it to a successor group. Our key analytic ingredient is a variance bound for Gaussian maxima: for a maximum of $m\geq 2$ centered linear forms with coefficient norms at most $r$, mean $\mu$, and variance $v$, we prove $v\leq r^2-\mu^2/(2\log m)$ using Chen's Gaussian convexity theorem. Together with a variance-scale lower-tail estimate, this controls the threshold loss at each extension, which shows that root-conditioned vector colorings can either extract a large independent set from a group or bound its size, forcing a contradiction after constantly many steps. The resulting sparse-case guarantee combines with the dense progress bound of Kawarabayashi, Thorup, and Yoneda, and the recursion's numerical inequalities are verified via rational interval arithmetic.

1 Introduction

The paper addresses polynomial-time coloring of promised 3-colorable graphs, developing a finite-depth Gaussian-cover recursion and proving an O(n^4/23)-coloring guarantee. Its analysis combines a variance-based cover-composition bound with root-conditioned shell rounding and exact finite verification.

1 Introduction

  • The problem asks how many colors suffice in polynomial time when a graph is promised 3-colorable but its three independent sets are not given.Five-coloring such graphs is NP-hard.Source: §1 · p. 2
  • A finite-depth recursion groups vertices by correlation with a fixed root, extends Gaussian covers across edges, and transfers them to successor shells.Large shells yield independent sets through rounding, while small shells impose cardinality bounds that constrain later extensions.Source: §1 · p. 2
  • The cover-composition analysis uses a Gaussian-maximum variance bound and Chen’s lower-deviation inequality to replace a full-radius enlargement cost with a variance-dependent factor.The remaining finite recursion inequalities are checked by exact rational interval arithmetic.Source: §1 · p. 2
  • O(n^4/23) colors suffice for every promised 3-colorable n-vertex graph, improving on the bounds of Bansal, Huang, and Lee and concurrent work by Narang and Tang.The algorithm runs in randomized polynomial time with success probability at least 1 − n^-10.Source: §1 · p. 2

1.1 Related work

  • Prior progress combined combinatorial and semidefinite methods, with KTY’s dense-case guarantee used alongside the paper’s sparse-case analysis.Earlier work includes the three-level neighborhood analysis of Bansal, Huang, and Lee; concurrent work by Narang and Tang also uses a fixed-depth Gaussian-cover recursion.Source: §1.1 · p. 3
  • The proof combines root-conditioned shell rounding from a three-round SoS relaxation with variance-based composition and exact drift verification to obtain exponent 4/23.The authors contrast their composition argument with prior use of Gaussian isoperimetry and concurrent use of Ehrhard’s inequality.Source: §1.1 · p. 3

2 Technical Background

The technical background supplies the vector-coloring and Gaussian-rounding tools, cover and packing machinery, Gaussian tail estimates, and dense–sparse progress framework used in the proof.

2.1 Vector colorings and Gaussian rounding

  • A vector κ-coloring assigns unit vectors whose edge inner products are at most −1/(κ − 1); the paper obtains vectors and consistent local coloring distributions from a symmetrized three-round SoS relaxation.Conditioning on a root gives correlations q_j with q_j ≥ −1/2 and q_j + q_k ≤ 1/2 on edges.Source: §2.1 · p. 4
  • KMS rounding thresholds Gaussian inner products to select vertices and removes conflicts; modified rounding uses a maximal matching, whose failure can expose large Gaussian maxima in tangent directions.The vector-coloring rounding result supplies an independent-set guarantee for graphs with bounded maximum degree.Source: §2.1 · p. 4, §2.2 · p. 5

2.2 Gaussian covers and packings

  • A Gaussian cover guarantees a lower bound on the maximum of Gaussian inner products with a direction family; cover failure in rounding yields such neighborhood covers.Covers can be converted to weighted packings, restricted while retaining witness mass, and pruned so outgoing cover properties persist under extension.Source: §2.2 · p. 5

2.3 Gaussian convexity and lower tails

  • Chen’s results give convexity of the normalized log moment-generating function and a variance-scale lower-tail bound, which the paper applies to maxima of linear forms to control cover-composition loss.The maximum is a convex Lipschitz Gaussian functional; its variance bound feeds the composition estimate.Source: §2.3 · p. 5

2.4 Dense–sparse progress and parameters

  • Progress toward coloring includes finding a large independent set, a small-boundary independent set, or same-colored vertices; dense–sparse combination joins degree-regime guarantees into a coloring algorithm.The paper sets a degree threshold and Gaussian rounding threshold for its sparse target, while slack absorbs shell-rounding and subpolynomial costs.Source: §2.4 · p. 6

3 Gaussian maxima and composition

This section develops Gaussian-maxima variance and lower-tail bounds and uses them to control Gaussian-cover composition, including root-shell rounding and repeated neighborhood lifts. It establishes finite initialization and uniform drift for the lifts, then uses endpoint-cover bounds to prove termination and derive the coloring exponent.

3 Gaussian maxima and composition

  • For F(g)=max⟨g,u_j⟩ over 1≤j≤m, with standard Gaussian g, m≥2, and ‖u_j‖≤r, let μ=EF and v=Var(F); for x≥0, Pr(F≤μ−x)≤exp(−x²/(2v)).Source: §3 · p. 6
  • An outer cover with an inner cover at each direction yields a joint witness with probability at least δ/2, while the variance bound controls the inner threshold loss.The norm-sensitive composition lemma assumes unit outer directions, at most ∆^A+o(1) outer vectors, and inner covers with threshold 3t−o(t) and probability t^-O(1); the resulting witness probability is t^-O(1).Source: §3 · pp. 7–8
  • Heavy correlation buckets preserve cover probability up to t^-O(1), projection loses at most log t in threshold, and bucket substitutions incur uniform o(t) threshold error.The projection guarantee applies to covers with probability at least t^-C; at fixed recursion depth, only polynomially many graph-indexed vectors are involved.Source: §3 · p. 9

3.1 Graph input and shell rounding

  • Root-shell rounding produces an independent set of expected size at least m^Δ−ρ(q)−o(1), uniformly across correlation buckets, and shells with every q_j > 1/4 are already independent.The rounding bound remains uniform under the stated inverse-polynomial SDP errors.Source: §3.1 · p. 10
  • Unless an expected-output alternative holds, every root-direction cover at correlation q and threshold Lt satisfies L^2 ≤ K(q)+o(1).This follows when full root-correlation shells are smaller than the shell-rounding size threshold.Source: §3.1 · p. 11

3.2 The repeated neighborhood lift

  • For selected heavy buckets and a matching outer class, the variance and correlation bounds are (2z + q)² ≤ 3d(1−q²) + o(1) and δ² ≤ d + o(1).The local-triple constraints are z ≥ −1/2 and q + z ≤ 1/2.Source: §3.2 · p. 12
  • The repeated lift preserves a successor-shell cover whose direction depends only on the root and endpoint, so repeated paths do not increase the number of directions beyond the shell size.Successors remain in G′, and the norm bound keeps the correlation parameter z a fixed distance from 1.Source: §3.2 · p. 13

3.3 Initialization and uniform drift

  • From each seed (b, η(a)), at most two generic lifts either violate a terminal cap or raise the threshold above T = 53/25.For continuing states, the certified drift exceeds 1/1000 uniformly over c ∈ [1/4, 1/4 + 10^-6]; interval checks terminate with 8,140 initialization boxes and 355 drift boxes.Source: §3.3 · pp. 14, 16

3.4 Termination, algorithm, and exponent

  • After at most 400 continuing lifts, the threshold reaches 2.44, contradicting the endpoint-family bound below 2.4 and forcing a rounding routine to succeed.The sparse algorithm tests the global rounding routine and all O(n log n) root-correlation shells.Source: §3.4 · p. 16
  • The two progress costs are n^{α+o(1)}; choosing α < α′ < 4/23 absorbs subpolynomial losses for sufficiently large n, and Theorem 2.6 of [BHL26] yields a proper coloring with eO(n^{α′}) colors.Finitely many smaller input sizes are absorbed into the constant in the asymptotic guarantee.Source: §3.4 · p. 19

4 Conclusion

The paper gives a randomized polynomial-time algorithm that colors promised 3-colorable graphs using O(n^4/23) colors. Its proof reduces sparse coloring to a scalar recursion whose positive drift is verified over a compact domain.

4 Conclusion

  • The algorithm colors promised 3-colorable graphs with O(n^4/23) colors in randomized polynomial time.The proof reduces sparse coloring to a scalar recursion on root correlation and cover threshold, with its positive drift verified by exact interval arithmetic.Source: §4 · p. 19
  • The recursion needs only an absolute-constant number of steps and rounds full root-correlation shells.Shell rounding limits the number of available endpoints.Source: §4 · p. 19
  • A variance bound for Gaussian maxima controls the loss at each recursion step.Source: §4 · p. 19

A Pruning with a fixed parameter buffer

The appendix uses an upper-degree pruning argument based on packing and spread. It interleaves vertex and edge deletions so the resulting covers are supported in one final graph.

A Pruning with a fixed parameter buffer

A.1 Packings and the auxiliary parameter

This appendix sets a fixed analysis parameter and uses an upper-degree condition to apply a spread theorem to outgoing families. The parameter buffer yields a positive asymptotic margin.

A.1 Packings and the auxiliary parameter

  • The analysis fixes c = c* and sets D = 3(1 + c), with ∆ an upper bound on the graph's maximum degree.Source: §A.1 · p. 22
  • The auxiliary parameter cpr is chosen fixed and sufficiently close to c, with cpr > c.The text identifies the resulting positive margin as 2(cpr − c)t^2 + o(t^2).Source: §A.1 · p. 22
  • The upper-degree bound |N(i)| ≤ ∆ ≤ Φ(s)^−(1+cpr) makes every outgoing family at most cpr-inefficient at threshold s for sufficiently large n.Source: §A.1 · p. 22

A.2 A retained graph with persistent two-walk supports

The appendix prunes weighted edges and vertices to obtain a nonempty retained graph. Its conclusions hold together in that final graph, preserving both a weight floor and the stated two-walk supports.

A.2 A retained graph with persistent two-walk supports

  • The buffered pruning starts with ε = 1/log log t and τ = ε^2 under the stated degree bound.Source: §A.2 · p. 22
  • The retained graph is nonempty and satisfies the stated per-vertex guarantee, with constants C1 and C2 depending only on cpr.The excerpt does not include the full per-vertex guarantee.Source: §A.2 · p. 22
  • Discarded edges are charged using symmetric weights, and every later neighborhood remains a subset of its Xi.Source: §A.2 · p. 23
  • The pruning repeatedly deletes a vertex with incident weight below r0 or deletes edges according to the triggering edge's neighborhood condition.Source: §A.2 · p. 23
  • At termination, every retained vertex has incident retained weight at least r0.Source: §A.2 · p. 24
  • The proved properties (15) and (16) hold in the same final graph, with their supporting neighbors still present.Source: §A.2 · p. 24

A.3 Matching weights and approximate edge correlations

The matching construction turns Gaussian-threshold selections into independent sets, and its packing inequalities remain valid under uniformly approximate edge correlations. These are the inequalities required by Lemma 19.

A.3 Matching weights and approximate edge correlations

  • The unmatched vertices of a maximal matching in the Gaussian-threshold set form an independent set.For exact unit vectors with edge inner product −1/2, the threshold set is Sg = {i : ⟨g, vi⟩ ≥ t}.Source: §A.3 · p. 24
  • The packing inequalities required by Lemma 19 follow from the matching-event argument and the resulting packing calculation.For a fixed vertex i, matching events indexed by its neighbors in A are disjoint; their union implies selection of i and that some direction in A reaches threshold 3t.Source: §A.3 · p. 25
  • Approximate edge correlations are handled using exact unit directions, while the matching weights remain symmetric because they are defined by undirected events.The endpoint directions may differ, but µi(j) = µj(i) still holds.Source: §A.3 · p. 25
  • The approximate-correlation argument preserves the packing calculation at a common threshold, with exact orthogonality and a parameter buffer yielding ∆ ≤ Φ(s) − (1 + cpr).The pruning proof relies on these packing inequalities, symmetry, unit norms, and the Gram-matrix calculation, which remain valid.Source: §A.3 · p. 25

A.4 Preservation of the finite initialization bound

The finite initialization implication persists when the auxiliary parameter is enlarged slightly beyond c. Compactness and continuity rule out failing tuples, so a fixed buffer is valid.

A.4 Preservation of the finite initialization bound

  • A strict finite implication says every admissible seed either violates a terminal cardinality bound or exceeds 53/25 after at most two lifts.The argument establishes persistence of this implication under a small fixed enlargement of the parameter.Source: §A.4 · p. 26
  • Compactness and continuity show that a sequence of failing perturbed tuples would converge to a tuple contradicting Proposition 17(1).The limiting tuple satisfies the unperturbed feasibility constraints but has neither a terminal violation nor a threshold above 53/25 within two lifts.Source: §A.4 · p. 26
  • Some fixed cpr > c is therefore valid; its numerical value is unnecessary for rounding, and the drift statement is unchanged.Small negative values of a are handled by continuity of the terminal loss at b = 1/4.Source: §A.4 · p. 26

A.5 Cover masses and uniform errors at depth 404

The depth-404 recursion controls cover-mass losses and uniform approximation errors. The retained mass remains inverse-polynomial, while vanishing errors preserve the strict drift used by the finite recursion.

A.5 Cover masses and uniform errors at depth 404

  • Pruning is performed once, with outgoing mass bounded below by a positive constant and initial two-walk mass at least 1/[2(log log t)^2].The fresh inner cover at each endpoint retains the constant mass supplied by pruning, so its probability bound does not deteriorate across earlier lifts.Source: §A.5 · p. 26
  • After 404 lifts, the retained outer cover mass remains at least t^-C for a fixed constant C.Projection and composition incur constant-factor costs, while bucket synchronization costs at most t^B in outer mass per lift.Source: §A.5 · p. 26
  • Scalar-bucket errors are controlled for graph-indexed families of unit directions whose size is at most n^b for fixed b.The family-size bound and Gaussian tail estimates provide the stated control for any A > 0.Source: §A.5 · p. 27
  • Uniform approximation errors vanish through the fixed-depth iteration, preserving a strict drift increment of at least 1/1250 for sufficiently large t.The normalized errors tend to zero uniformly over depths h ≤ 404.Source: §A.5 · p. 27

B Weighted composition and entropy

The appendix gives a weighted version of cover composition that tracks individual branch masses as well as total mass. It distinguishes average logarithmic loss from the stronger uniform control needed across branches.

B Weighted composition and entropy

  • The weighted composition setup assigns each positive-mass index a normalized weight πj and logarithmic branch loss aj from its mass relative to p.The cover has total mass δ, and p = Φ(s).Source: B Weighted composition and entropy · p. 27
  • The composition argument obtains a joint witness by combining an outer hit with an inner success, using independence of the inner maximum from the outer direction.Under the stated mean and variance conditions, the joint-witness probability is at least (1 − η − ϵ)δ.Source: B Weighted composition and entropy · pp. 27–28
  • For an outer cover of probability δ, the argument bounds the loss of an arbitrary cover without assuming a uniform packing.In a uniform packing, the branch loss is constant and no truncation is needed.Source: B Weighted composition and entropy · p. 29
  • Shannon entropy captures average logarithmic branch loss but does not control every branch; a uniform bound requires truncation at a stated 1/η factor.The weighted argument distinguishes individual branch losses from a uniform threshold.Source: B Weighted composition and entropy · pp. 27, 29
  • The present proof uses Chen’s variance-scale lower tail with per-index independence and a union bound, contrasting with Borell enlargement and the Ehrhard-based bound.The passage relates the alternatives to Bansal, Huang, and Lee [BHL26, Lemma 4.14] and Narang and Tang.Source: B Weighted composition and entropy · p. 29
Loading 2610.01071v1…