History and comparison with prior work

The difficulty of approximate coloring persists even with a very small promised palette. Khanna, Linial, and Safra established hardness of four-coloring three-colorable graphs (Khanna et al. 2000); Guruswami and Khanna later gave a different proof and obtained bounded-degree and edge-error variants (Guruswami and Khanna 2004). The algebraic theory of promise constraint satisfaction developed by Barto, Bulı́n, Krokhin, and Opršal gave hardness of \((2k-1)\)-coloring \(k\)-colorable graphs, and hence five colors when \(k=3\) (Barto et al. 2021, Theorem 6.5). Their Example 2.9 records the conjectured hardness for every fixed \(3\le k\le c\).

Guruswami and Sandeep showed that the ordinary \(d\)-to-\(1\) Games Conjecture with perfect completeness, for any fixed \(d\ge2\), implies constant-palette hardness for three-colorable graphs (Guruswami and Sandeep 2020, Theorem 1). Their reduction first gives arbitrarily small independent-set density with a \(2d\)-colorable completeness promise (Guruswami and Sandeep 2020, Theorem 9). The arc-graph reduction of Krokhin, Opršal, Wrochna, and Živný (Krokhin et al. 2023, Theorem 1.8) then reduces the promised palette to three for the coloring conclusion. The resulting three-colorable hardness statement does not include the independent-set guarantee. The companion article (OpenAI 2026, Theorem 1.1) establishes the ordinary perfect-completeness premise for \(d=2\).

Fei, Minzer, and Wang have proved the \(4\)-to-\(1\) Games Conjecture with perfect completeness (Fei et al. 2026, Theorem 1.6). Combining it with the preceding reductions resolves the constant-palette conjecture: their Corollary 1.7 gives the three-colorable versus not \(c\)-colorable gap for every fixed \(c\). Their Corollary 1.9 gives arbitrarily small independent-set density with an eight-colorable completeness promise, corresponding to \(2d=8\). Theorem 1 combines this stronger form of soundness with three-colorability of the entire graph. Our proof starts with ordinary projection Label Cover and does not require a bound on projection-fiber sizes.

The distinction between colorability and independence density also appears in earlier conditional results. Dinur, Mossel, and Regev obtained three-colorable completeness and arbitrarily small independent-set soundness from their fish-shaped Label Cover conjecture (Dinur et al. 2009, Conjecture 4.8 and Sections 4.3–4.5). Braverman, Khot, Lifshitz, and Minzer obtained the same graph promise from the Rich \(2\)-to-\(1\) Games Conjecture using their invariance principle for the multi-slice (Braverman et al. 2022, Corollary 1.19). The Rich condition requires that, at each left question, a uniformly random incident constraint induce a uniformly random partition of the left alphabet among all partitions into pairs. This is not part of the ordinary \(2\)-to-\(1\) premise above.

A different line of work relaxes completeness by permitting deletion of a small fraction of vertices. Dinur, Khot, Perkins, and Safra proved that, for arbitrarily small fixed \(\varepsilon>0\), it is NP-hard to find an independent set of density \(1/9\) when an induced three-colorable subgraph occupies at least \((1-\varepsilon)n\) vertices (Dinur et al. 2010). Hecht, Minzer, and Safra subsequently proved, under randomized reductions, hardness of almost coloring such almost-three-colorable graphs with any fixed palette (Hecht et al. 2023). The all-vertex completeness in Theorem 1 retains the original coloring promise, while allowing every fixed positive soundness density.

Algorithmic work gives a complementary perspective on the remaining quantitative gap. Bansal, Huang, and Lee give a polynomial-time algorithm using \(O(n^{0.19539})\) colors (Bansal et al. 2026), improving the \(\widetilde O(n^{0.19747})\) bound of Kawarabayashi, Thorup, and Yoneda (Kawarabayashi et al. 2024). In preprints posted after the September 24 version of this manuscript, Narang and Tang report a randomized polynomial-time bound of \(O(n^{(13-\sqrt{97})/18+\varepsilon})\) for each fixed \(\varepsilon>0\) (Narang and Tang 2026), and Anand reports a randomized polynomial-time bound of \(O(n^{4/23})\) (Anand 2026). Our reduction has fixed \(\delta\) and fixed palettes; its polynomial exponent can depend on these constants.

Proof overview and method ancestry

The starting problem is Label Cover: a bipartite collection of questions and tests, each prescribing a projection from a left answer to a right answer. The PCP theorem and parallel repetition supply instances in which either every test can be satisfied or every labeling succeeds on at most an arbitrarily small fixed fraction of tests (Arora et al. 1998; Raz 1998; Dinur and Steurer 2014).

We replace one left question at a time by a right question, obtaining chains of question tuples. This use of layered tuples and projection constraints is related to the multilayered PCP construction of Dinur, Guruswami, Khot, and Regev (Dinur et al. 2005). At each tuple, a point assigns a phase in \(\mathbb T=\mathbb R/\mathbb Z\) to every possible product answer. An answer projection \(\pi:M\to M'\) pulls a phase vector \(x\in\mathbb T^{M'}\) back to \(x\circ\pi\in\mathbb T^M\). Link these two points with length zero, and link points within each phase space with their sup circle distance. Shortest paths through these links define a pseudometric. Edges compare one point with the coordinatewise half-shift of another. A satisfying Label Cover labeling evaluates each phase assignment at one product answer. This evaluation is nonexpanding, and the edge threshold forces adjacent vertices to have circle phases more than \(1/3\) apart. Three equal half-open intervals of the circle therefore color all vertices properly.

For soundness, an independent set gives bounded functions on the tuple phase spaces that change sign under a half-shift and satisfy a common Lipschitz bound. Austin’s dimension-independent approximation theorem (Austin 2016), a continuous counterpart of Friedgut’s junta theorem (Friedgut 1998), approximates these functions using boundedly many answer coordinates. The difficulty is that approximation under product measure need not survive identifications of coordinates by projections. We therefore choose coordinate lists for whole small subchains and introduce independent rotation variables at every layer of each subchain. All required compatibility properties are proved within this paper. Projecting the selected coordinates to the last layer places all lists in a common answer set. A shared answer for two separated subchains supplies compatible answers to an intervening Label Cover test, so low source value makes these intersections rare.

Two further steps turn this structural information into a density bound. First, a distributional alignment lemma chooses a law on sets of layers before seeing the lists. On most selected sets, each listed label can be assigned to an index shared by all its occurrences. The bound is independent of the label universe. The proof combines finite minimax, Ramsey homogenization of finite probability patterns, and an order-invariant random-array argument. The homogenization step has antecedents in the Ramsey theory of random variables (Trotter and Winkler 1998); we give the particular alignment argument in full.

Second, we sample coefficients at finitely many levels between \(0\) and \(1\), with geometrically decreasing probabilities. Enough layers make a coefficient equal to \(1\) likely. That layer absorbs auxiliary uniform phase shifts without changing their distribution. Alignment makes dependence on a zero-coefficient layer small; decreasing a positive coefficient by one level bounds its probability of substantial dependence. A dimension-independent bound on influential coordinates then gives a small mean square, and hence a small independent-set density.

Only fixed finite rational data enter the graph construction. The probability experiment is expanded exactly into unweighted vertices, so the reduction is deterministic. Section 2 states the standard inputs and derives the analytic coordinate bounds. Section 3 constructs the graph with finite parameters and proves completeness. Section 4 extracts the coordinate lists from an independent set and decodes intersections of separated lists. Section 5 states distributional alignment and applies it to these lists. Section 6 proves the coefficient estimate under explicit inequalities, and Section 7 chooses all constants in dependency order and completes Theorem 1. The self-contained proof of distributional alignment is given in Section 8.

A projection constraint problem

A Label Cover instance consists of finite question sets \(U,V\), nonempty finite answer alphabets \(\Sigma_L,\Sigma_R\), and a nonempty explicit list \(\mathcal C\) of test occurrences. An occurrence \(c\) has questions \(u_c\in U\), \(v_c\in V\), and a total map \(\pi_c:\Sigma_L\to\Sigma_R\). The value is \[\mathop{\mathrm{val}}(\mathcal C)= \max_{\ell:U\to\Sigma_L,\ \rho:V\to\Sigma_R} \Pr_{c\in\mathcal C}\bigl[\pi_c(\ell(u_c))=\rho(v_c)\bigr],\] where occurrences, including repeated occurrences, are sampled uniformly.

This is the standard consequence of the PCP Theorem and parallel repetition (Arora et al. 1998; Raz 1998). A quantitative statement is (Dinur and Steurer 2014, Theorem 6.2, full version): for a fixed number \(k\) of repetitions, the output size is \(n^{O(k)}\), the alphabet size is at most \(a^k\), and the soundness is at most \(\beta_0^k\), for absolute constants \(a>1\) and \(0<\beta_0<1\). Choose a fixed \(k\) for which \(\beta_0^k\le\sigma\). The unweighted total-projection formulation is explicitly recorded in (Dinur et al. 2025, Definitions 1.1–1.2 and Theorem 1.3). The latter source even supplies \(d\)-to-one maps, a property we do not use. Here the verifier’s random choices specify an explicit list of constraints; they are not random choices of the reduction. Unused questions can be removed.

Juntas for the sup metric

A function is a junta on \(S\) if it depends only on the input coordinates in \(S\). The approximating functions below need not be continuous. We use Austin’s continuous junta theorem (Austin 2016), which extends the dimension-independent coordinate approximation phenomenon of Friedgut’s Boolean junta theorem (Friedgut 1998).

To obtain this formulation from (Austin 2016, Theorem 1.1, arXiv version 4), use the usual interval with uniform measure and modulus of continuity \(\omega(t)=Lt\). The interval is compact, connected, and locally connected, as required there. Austin’s theorem gives \(\|f-\mathbb E[f\mid X_S]\|_1<\tau^2/2\) with \(|S|\) bounded independently of \(N\). Both functions take values in \([-1,1]\), so \[\|f-\mathbb E[f\mid X_S]\|_2^2 \le 2\|f-\mathbb E[f\mid X_S]\|_1<\tau^2.\] The bound applies to pullbacks of torus functions, since the quotient \([0,1]^N\to\mathbb T^N\) is nonexpanding and preserves the product uniform law.

For a square-integrable function \(H\) of independent circle coordinates \(z_1,\ldots,z_s\), let \(E_i\) average coordinate \(z_i\) alone, and set \[Q_i=\mathop{\mathrm{id}}-E_i,\qquad D_i(H)=\|Q_iH\|_2.\] Both \(E_i\) and \(Q_i\) are orthogonal projections. In particular, \(\|Q_if\|_2\le\|f\|_2\); the constant here is one.

The first part locates a coordinate when the function has substantial variance; the second limits how many coordinates can have a smaller but still fixed amount of dependence. Their simultaneous dimension independence is what will permit the number of test blocks to be chosen after both bounds are fixed.

Tuples, grids, and zero-length links

Let \(\mathcal C\) be any Label Cover instance, with unused questions removed. In layer \(i\in[r]\), take all question tuples \[\mathbf q=(v_1,\ldots,v_{i-1},u_i,\ldots,u_{r-1}) \in V^{i-1}\times U^{r-i}.\] The answer set of such a tuple is \[M_i=\Sigma_R^{\,i-1}\times\Sigma_L^{\,r-i}.\] Layered products of questions with projection constraints also occur in the multilayered PCP construction of (Dinur et al. 2005). Here each position is a separate coordinate even if question names repeat. Different tuples in a layer use separate copies of this same answer set.

Between adjacent layers \(i\) and \(i+1\), impose a map whenever the tuples agree outside position \(i\) and their questions at position \(i\) are the endpoints of a test occurrence \(c\). The map on answer sets applies \(\pi_c\) in position \(i\) and the identity in every other position. Impose it separately for every occurrence.

Write \(\Gamma=(D^{-1}\mathbb Z)/\mathbb Z\). At each question tuple place a separate copy of \(\Gamma^{M_i}\), and let \(\mathscr X\) be their disjoint union. Make a finite undirected weighted link graph on \(\mathscr X\):

• Within each copy, link any two points with length their sup circle distance.

• For every imposed map \(\pi:M_i\to M_{i+1}\), link each target point \(x\in\Gamma^{M_{i+1}}\) to its source pullback \(x\circ\pi\) with length zero.

Let \(\mathop{\mathrm{dist}}\) be the resulting shortest-path extended pseudometric, with distance infinity between components. Thus distinct points may have distance zero.

Let \(T\) add \(1/2\) to every phase coordinate, within each copy. Since \(D\) is even, \(T\) permutes \(\mathscr X\) and satisfies \(T^2=\mathop{\mathrm{id}}\). It preserves all link lengths and therefore is an isometry of \(\mathop{\mathrm{dist}}\).

If some \(x\in\mathscr X\) satisfies \[ \mathop{\mathrm{dist}}(x,Tx)\le1/8, \tag{2}\] output \(K_q\) and stop. This branch already has independent-set density \(1/q<\delta\). We will show that it never occurs in completeness.

Vertices and edges

If (2) fails for every point, consider the following finite experiment.

1. Sample \(r-1\) independent uniform occurrences \(c_1,\ldots,c_{r-1}\), with questions \((u_h,v_h)\) at position \(h\). They determine a chain of tuples \[\mathbf q_i=(v_1,\ldots,v_{i-1},u_i,\ldots,u_{r-1}), \qquad i\in[r].\] Write \(\pi_{ij}:M_i\to M_j\) for the corresponding composite answer maps. They apply the test projections in positions \(i,\ldots,j-1\) and leave the other positions unchanged; in particular they are composition-consistent.

2. Independently choose \(B\sim\mu\). For every \(j\in B\), independently choose \(t_j\) from (1), and choose independent rotation entries \[\widehat\theta_{j,\ell}\ \text{uniform in }\ \{0,1/P,\ldots,(P-1)/P\},\qquad \ell\in M_j .\]

3. With \(b=\min B\), give the outcome the location \[ x=\left( \sum_{j\in B}t_j\widehat\theta_{j,\pi_{bj}(\kappa)} \pmod1\right)_{\kappa\in M_b} \in\Gamma^{M_b} \tag{3}\] in the copy at tuple \(\mathbf q_b\).

Take distinct output vertices for these elementary outcomes with integer multiplicities that make the experiment their exact uniform law. The existence and size of these multiplicities are verified below. Different vertices may have the same location. For distinct vertices with locations \(x,y\), put an edge precisely when \[ \mathop{\mathrm{dist}}(x,Ty)\le1/8. \tag{4}\] This is symmetric because \(T\) is an involutive isometry: \(\mathop{\mathrm{dist}}(x,Ty)=\mathop{\mathrm{dist}}(Tx,y)=\mathop{\mathrm{dist}}(y,Tx)\).

Figure 1 shows how the two parts of the construction serve this coloring: projection links preserve the evaluated phase, whereas an output edge separates its endpoint phases by more than the length of a color interval.

Odd functions and compatibility

Let \(A\subseteq\mathscr X\) be the set of locations of vertices in \(\mathcal A\), with multiplicities removed. Then \[ \mathop{\mathrm{dist}}(A,TA)>1/8. \tag{5}\] For locations of distinct selected vertices this follows from the missing edge in (4). For a point compared with itself, it follows from exclusion of (2). Since the sets are finite, these pointwise strict inequalities give (5), including when distances are infinite.

On \(\mathscr X\) define \[ f(x)=\bigl(1-32\mathop{\mathrm{dist}}(x,A)\bigr)_+ -\bigl(1-32\mathop{\mathrm{dist}}(Tx,A)\bigr)_+, \qquad (u)_+=\max\{u,0\}, \tag{6}\] with each bump defined to be zero at infinite distance. This function takes values in \([-1,1]\), satisfies \(f(Tx)=-f(x)\), and equals \(1\) on \(A\). It is constant across every zero link. Within each grid copy it is \(64\)-Lipschitz for the sup circle metric: distance to \(A\) is \(1\)-Lipschitz on a component meeting \(A\), and its bump is identically zero on a component not meeting \(A\). Also the shortest-path pseudometric never exceeds a within-copy link distance.

At each tuple \(\mathbf q\), extend its grid function to the whole torus \(\mathbb T^{M_i}\). Using the real-valued Lipschitz extension formula of McShane (McShane 1934), set \[g_{\mathbf q}(x)= \min_{y\in\Gamma^{M_i}} \bigl(f(y)+L\,d_\infty(x,y)\bigr),\] where \(y\) ranges over that tuple’s copy and \(d_\infty\) is the sup circle metric. This is \(L\)-Lipschitz and equals \(f\) on the grid. Clip its values to \([-1,1]\), obtaining \(\widetilde g_{\mathbf q}\), and put \[F_{\mathbf q}(x)= \frac{\widetilde g_{\mathbf q}(x) -\widetilde g_{\mathbf q}(Tx)}2.\] The resulting function is still an extension of the odd grid data, is \(L\)-Lipschitz, is valued in \([-1,1]\), and is odd under \(T\). Fix this entire family of functions before sampling any test chain. Along a chain write \(F_i=F_{\mathbf q_i}\).

For every chain and every \(i\le j\), these extensions satisfy \[ |F_j(x)-F_i(x\circ\pi_{ij})| \le 2L/D,\qquad x\in\mathbb T^{M_j}. \tag{7}\] Indeed, round each coordinate of \(x\) once to a grid point \(y\) within \(1/D\). Pullback does not enlarge this error. The grid points \(y\) and \(y\circ\pi_{ij}\) have equal \(f\) values by the chain of zero links, so the two extension errors total at most \(2L/D\). Intermediate layers contribute no additional approximation error.

Bounded lists for a subchain

The functions \(F_i\) now supply the analytic data we need along any chain. For each small set of layers, we will choose a bounded list of answer coordinates that approximates every allowed coefficient choice. The bound must be independent of the Label Cover alphabets, and the choice must depend only on the data of that subchain.

Fix an approximation tolerance \(\gamma>0\). For \(\varnothing\ne I\subseteq[r]\) with \(|I|\le s\), put \(b_I=\min I\). Given \(t\in\mathcal T_m^I\), define \[ h_{I,t}(\theta) =F_{b_I}\left( \left(\sum_{j\in I}t_j\theta_{j,\pi_{b_Ij}(\kappa)} \pmod1\right)_{\kappa\in M_{b_I}}\right), \qquad \theta\in\prod_{j\in I}[0,1]^{M_j}. \tag{8}\] The entries of \(\theta\) are independent uniform real variables. This evaluates \(F_{b_I}\) at the continuous version of the sampled location in (3), using only the layers of \(I\). The phase map has Lipschitz constant at most \(|I|\le s\): coordinate duplication by a projection cannot enlarge a sup distance. Thus \(h_{I,t}\) is \(sL\)-Lipschitz, independently of the label-set sizes and projection fibers.

Why the lists can be decoded locally

Use the fixed rule of Lemma 8 along a uniform occurrence chain. Using \(M_r=\Sigma_R^{r-1}\) as a common label universe, set \[ A_I=\bigcup_{j\in I}\pi_{jr}(S_I^j), \qquad \varnothing\ne I\subseteq[r],\quad |I|\le s. \tag{11}\] By (9), each \(A_I\) has size at most \(d\). We first control intersections between lists on separated sets of layers.

The fixed functions may depend on the entire instance and on \(\mathcal A\). This causes no loss of locality: they are fixed before the sampling experiment, so evaluating the family at a tuple reveals only that tuple. In particular, if two occurrences have the same own question but different opposite questions or projections, the list rule at that side uses identical data.

We have obtained bounded lists in a common answer set, and source soundness controls intersections of lists on separated layer sets. The next section turns this separation into a stronger property: each listed answer can be assigned to one layer common to all of its occurrences inside the sampled set \(B\).