betaFeedback

WorksComputer Science

Circle configurations and the hardness of promise graph and hypergraph coloring

Abstract

In 2017 Brakensiek and Guruswami conjectured that promise graph homomorphism is NP-hard for every non-bipartite source and loopless target admitting a homomorphism from the source. At CCC 2016 they conjectured hardness of properly coloring a uniform hypergraph promised a strong coloring with one more color than its uniformity. We prove both conjectures by a configuration theorem on the circle. For any fixed finite configuration of distinct rational phases, the theorem gives a reduction whose satisfiable instances place every edge near a translate of the configuration and whose unsatisfiable instances have arbitrarily small independence ratio. An antipodal pair gives hardness for every odd cycle against every fixed clique of size at least three. A regular hh-gon gives a strong (h+1)(h+1)-coloring and a rainbow (h−1)(h-1)-coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of PCSP(R,NAEh(d))\mathrm{PCSP}(R,\mathrm{NAE}_h^{(d)}) for every nonempty symmetric reconfigurable relation RR with R→NAEh(d)R\to\mathrm{NAE}_h^{(d)}, and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich 22-to-11 Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes 3≤c≤d3\le c\le d. The proof subtracts an average of translated distance functions to detect an independent set, then uses conditional mean zero and a finite Ramsey alignment argument to decode a Label Cover assignment.

Introduction

For finite relational structures A→BA \to B, the decision problem PCSP⁡(A,B)\operatorname{PCSP}(A,B) accepts inputs XX with a homomorphism X→AX \to A and rejects inputs XX with X↛BX \not\to B. A homomorphism preserves every relation. For graphs it sends each edge to an edge. Taking AA and BB to be cliques gives approximate graph coloring.

For a hypergraph HH, let α(H)\alpha(H) be the maximum size of a set containing no entire edge. A proper coloring partitions the vertices into independent sets. A strong coloring gives distinct colors to all vertices of each edge. A rainbow coloring requires every edge to see every color of the specified palette. We use finite simple hypergraphs. An edge of uniformity hh is a set of hh distinct vertices.

Write T=R/Z\mathbb{T} = \mathbb{R}/\mathbb{Z} and give it the distance dT(a,b)=min⁡n∈Z∣a−b−n∣d_{\mathbb{T}}(a,b) = \min_{n \in\mathbb{Z}} |a-b-n|, computed with real lifts. The phase map in the following theorem is one map on the entire vertex set. Only the translation and the ordering vary from edge to edge.

Theorem 1.1 (Configuration theorem). Fix h≥2h \ge2, distinct rational offsets u0=0,u1,…,uh−1u_0 = 0, u_1, \ldots, u_{h-1} in T\mathbb{T}, a rational ρ>0\rho> 0 such that

2ρ<min⁡i≠jdT(ui,uj),2\rho< \min_{i \ne j} d_{\mathbb{T}}(u_i,u_j),

and a real δ>0\delta> 0. There is a deterministic polynomial-time reduction from 3SAT to nonempty hh-uniform hypergraphs HH with these properties.

(i) If the input is satisfiable, there is a map φ:V(H)→T\varphi: V(H) \to\mathbb{T}. Every edge has an ordering x0,…,xh−1x_0,\ldots,x_{h-1} and a t∈Tt \in\mathbb{T} for which

dT(φ(xj),t+uj)≤ρ(0≤j<h).d_{\mathbb{T}}(\varphi(x_j),t+u_j) \leq\rho\qquad(0 \leq j < h).

(ii) If the input is unsatisfiable, then α(H)<δ∣V(H)∣\alpha(H) < \delta|V(H)|.

The reduction outputs an explicit unweighted hypergraph. Its polynomial degree and constants may depend on the fixed data.

Coloring consequences

The first two applications use equal half-open intervals of the circle. For an odd cycle, their cyclic order matters. For a regular polygon, two partitions of different widths read different colorings from the same phase map.

Corollary 1.2 (Odd cycles and graph homomorphisms). For every odd g≥3g \geq3 and every 0<δ<1/30 < \delta< 1/3, there is a deterministic polynomial-time reduction from 3SAT to nonempty graphs such that satisfiable instances map to CgC_g and unsatisfiable instances have independence ratio less than δ\delta. Consequently PCSP(CgC_g, KcK_c) is NP-hard for every c≥3c \geq3. More generally, PCSP(AA, BB) is NP-hard for every pair of finite loopless undirected graphs A→BA \to B with AA non-bipartite.

The last statement is Conjecture 1.2 of Brakensiek and Guruswami in the April 2017 revision of ECCC TR16-183 [8]. The bound δ<1/3\delta< 1/3 keeps the two promises disjoint for every CgC_g. Indeed, write g=2k+1g = 2k + 1. A uniform rotation of a fixed independent kk-set of CgC_g contains each vertex with probability k/gk/g. Its preimage under X→CgX \to C_g has expected size k∣V(X)∣/g≥∣V(X)∣/3k|V(X)|/g \geq|V(X)|/3.

Corollary 1.3 (Strong and rainbow colorings). For every h≥3h \geq3 and δ>0\delta> 0, a deterministic polynomial-time reduction from 3SAT produces an hh-uniform hypergraph with a strong (h+1)(h+1)-coloring and a rainbow (h−1)(h-1)-coloring in the satisfiable case, and independence ratio below δ\delta in the unsatisfiable case.

For all fixed kk, c≥2c \geq2 except (k,c)=(2,2)(k,c) = (2,2), it is NP-hard to find a proper cc-coloring of a kk-uniform hypergraph promised to be strongly (k+1)(k+1)-colorable. For k≥3k \geq3 this also holds under the rainbow (k−1)(k-1)-coloring promise and under both promises together.

The strong-coloring assertion settles CCC 2016 Conjecture 1.2. The rainbow boundary was posed separately in the table on page 14:4 of the same paper [7].

For a palette of size dd, let NAEh(d)\mathrm{NAE}_h^{(d)} be the relation of nonconstant hh-tuples. A relation is symmetric if it is closed under coordinate permutations. It is reconfigurable if any two of its tuples are joined inside the relation by a path whose steps change one coordinate. We identify a relation with its one-relation structure.

Write Fk(c)\mathcal{F}_k^{(c)} for the family consisting of a monochromatic kk-clique in each of cc colors. An arrow Fk(c)→Fℓ(d)\mathcal{F}_k^{(c)} \to\mathcal{F}_\ell^{(d)} means that a fixed map of palettes takes every coloring avoiding the first family to a coloring avoiding the second. The corresponding PMSNP problem accepts graphs admitting the first coloring and rejects graphs admitting no second coloring [6].

Corollary 1.4 (Reconfigurable relations and monochromatic cliques). Let R⊆AhR \subseteq A^h be a nonempty symmetric reconfigurable relation on a finite set, where h≥2h \geq2. For every dd with R→NAEh(d)R \to\mathrm{NAE}_h^{(d)}, the problem PCSP(R,NAEh(d)R,\mathrm{NAE}_h^{(d)}) is NP-hard.

Let cc, dd, kk, ℓ\ell be positive integers with Fk(c)→Fℓ(d)\mathcal{F}^{(c)}_k \to\mathcal{F}^{(d)}_\ell. If ℓ≥c(k−1)\ell\ge c(k-1), then PMMSNP⁡(Fk(c),Fℓ(d))\operatorname{PMMSNP}(\mathcal{F}^{(c)}_k,\mathcal{F}^{(d)}_\ell) is solvable in polynomial time via affine integer programming. If ℓ<c(k−1)\ell< c(k-1), then it is NP-hard.

A linearly ordered coloring gives each edge a unique vertex of maximum color. Let LOc\mathrm{LO}_c denote the relation of triples with a unique maximum on an ordered cc-element palette.

Corollary 1.5 (Linearly ordered triples). For every fixed 3≤c≤d3 \le c \le d, the problem PCSP⁡(LOc,LOd)\operatorname{PCSP}(\mathrm{LO}_c,\mathrm{LO}_d) on 33-uniform hypergraphs is NP-hard.

Proof overview

A point in a phase grid assigns one circle value to each possible answer of a question tuple. An answer projection π\pi lifts a phase vector yy to y∘πy \circ\pi. We give this link length zero. Moving within a grid costs the maximum change in any coordinate. A satisfying assignment chooses a coordinate in every grid, compatibly with every projection. Evaluating that coordinate gives a circle map that cannot increase path length. Adding uu to every coordinate adds uu to the evaluation. We can therefore test a configuration by looking for one grid point ww near whose prescribed translates the vertices of an edge all lie.

The layered Label Cover framework with phase grids, list decoding, and distributional alignment was introduced by OpenAI in item 106 for the independent-set gap on three-colorable graphs [26]. The accompanying scope document describes the Lean formalization of that graph theorem [31].

Consider an independent set and let bb be a truncated distance function equal to one at its locations. At a selected location xx, at least one of the translates of xx must have bump value zero. Otherwise the nearby selected vertices would form an edge. Thus the difference between b(x)b(x) and the average of its translated values is at least 1/h1/h. Extend the bump to the torus before taking this difference. The resulting function has integral zero on every diagonal circle, including circles of product measure zero.

The sampled vertex combines several layers. Each layer contributes independent rotation entries, multiplied by a coefficient in {0,1/m,…,1}\{0, 1/m, \ldots, 1\}. These real rotation entries give a product space even when answer projections identify many coordinates. Austin’s theorem approximates the function of the rotations by a function depending on boundedly many entries. Their indices are answer lists. If two lists from separated layer sets project to a common final answer, they give compatible candidates on the two sides of a single Label Cover test. Small Label Cover value makes such intersections rare.

The remaining issue is to assign a layer to every final answer. When layer ii has coefficient zero, we use the list for the other layers. A final answer in that list must be assigned somewhere other than ii. A finite Ramsey argument chooses a distribution on layer sets before the lists are known. With high probability all these assignments can be made at once. The proof uses the fact that a label occurring on several lists has a point common to the intervals spanned by their index sets. Two test points in a gap between indices control the probability of rounding this point to the deleted index.

Give each chosen layer an auxiliary uniform phase. Each answer reads the auxiliary phase of its assigned layer. Simultaneously translating these phases translates every input coordinate, so the function of the auxiliary phases has mean zero for each fixed choice of the rotations and coefficients. A large mean square forces an influential layer. A coefficient equal to one can absorb all the auxiliary phases. This makes a zero-coefficient layer nearly uninfluential by the assignment property. At a positive coefficient, decreasing the coefficient by one level changes the function very little. The geometric law on levels and a bound on the number of influential layers make this second possibility rare as well. The mean square bound passes to the grid and bounds the density of the independent set.

Related work

Hell and Nešetřil classified the complexity of homomorphisms to a fixed undirected graph. A loopless target gives a polynomial-time problem when it is bipartite and an NP-complete problem otherwise [25]. The approximate coloring problem goes back to Garey and Johnson [20]. Krokhin, Opršal, Wrochna, and Živný observed that the graph promise conjecture is equivalent to hardness for all odd cycles against all fixed cliques of size at least three [29].

Khanna, Linial, and Safra proved hardness of four-coloring a three-colorable graph [27]. Guruswami and Khanna gave another proof and obtained bounded-degree hardness [21]. For aa-colorable inputs, a≥3a \ge3, Brakensiek and Guruswami reached 2a−22a - 2 colors [7]. Bulín, Krokhin, and Opršal reached 2a−12a - 1, including five colors at a=3a = 3 [11, 5]. Krokhin and Opršal proved hardness against K3K_3 for every non-bipartite three-colorable source [28]. Wrochna and Živný reached (a⌊a/2⌋)−1\binom{a}{\lfloor a/2\rfloor} - 1 colors for a≥4a \ge4. Their topological method also gives hardness for square-free targets and circular cliques of ratio strictly between two and four [37, 29]. Krokhin, Opršal, Wrochna, and Živný’s arc-graph reduction shows that hardness against all constant palettes for one fixed clique source implies the same result for K3K_3 [29 Theorem 1.8]. Avvakumov, Filakovský, Opršal, Tasinato, and Wagner proved hardness against K4K_4 for every non-bipartite four-colorable source, settling the conjecture for four-colorable targets [4].

Dinur, Mossel, and Regev obtained three-colorable completeness and small independent sets from their fish-shaped Label Cover conjecture [14]. Under ordinary perfect-completeness dd-to-1 hardness, Guruswami and Sandeep obtained the density gap with 2d2d-colorable completeness and constant-palette hardness with three-colorable completeness [23, 29]. Fei, Minzer, and Wang proved perfect-completeness 4-to-1 hardness. Their Corollaries 1.7 and 1.9 give, respectively, constant-palette hardness for three-colorable graphs and the density gap for eight-colorable graphs [18]. OpenAI’s ordinary perfect-completeness 2-to-1 theorem also implies the constant-palette conclusion by the preceding reductions [19, 23, 29]. In the odd-cycle versus clique formulation, these results leave odd g≥5g \ge5 against c≥5c \ge5.

Braverman, Khot, Lifshitz, and Minzer derived the three-colorable density gap from the Rich 2-to-1 Games Conjecture [10]. Banakh, Barsukov, and Nakajima observed that their conditional Theorem 8 implies the full graph conjecture [6]. Richness concerns the distribution at a fixed left question. Braverman et al. require a uniform partition into pairs. Banakh et al. require uniformity over the labeled two-to-one maps. Ordinary two-to-one hardness specifies the fiber sizes [10 Definition 1.16][6 Definition 27].

For strong colorings, Brakensiek and Guruswami proved two-color hardness with ⌈3k/2⌉\lceil3k/2\rceil strong colors for every k≥3k \ge3, and with k+1k + 1 strong colors for k=3,4k = 3, 4 [7 Theorem 1.3]. Under their induced V Label Cover conjecture, they obtained separate density gaps for ⌈k+k−1/2⌉\lceil k + \sqrt{k} - 1/2\rceil strong colors when k≥2k \ge2, and k−1k - 1 rainbow colors when k≥3k \ge3 [9 Theorem 1.2 and footnote 6]. Guruswami and Lee obtained small independent sets under an almost balanced rainbow promise [22]. Austrin, Bhangale, and Potukuchi proved two-color hardness with k−2⌊k⌋k - 2\lfloor\sqrt{k}\rfloor rainbow colors in the range where this is a rainbow promise, and settled the boundary k−1k - 1 for k=4k = 4 [1]. Guruswami and Sandeep extended boundary two-color hardness to k=5,6k = 5, 6 [24].

For triples, rainbow two-colorability is ordinary two-colorability. Dinur, Regev, and Smyth proved hardness against every constant proper palette under this promise [15]. Also, pairing the colors of a strong four-coloring gives a rainbow two-coloring. Thus the k=3k = 3 strong-coloring result of Brakensiek and Guruswami already supplied both promises for two-color hardness. The original ECCC abstract of Fei, Minzer, and Wang, posted September 14, 2026, announced the density gap for ordinary two-colorable triples. It is Corollary 1.10 of their full paper [18].

Banakh, Barsukov, and Nakajima proved the two statements of Corollary 1.4 under the Rich 2-to-1 Conjecture. We use their LICS numbering. Theorems 5, 8, and 9 and Corollary 10 correspond to Theorems 1.5, 1.8, and 1.13 and Corollary 1.14 in the second arXiv version [6]. Their Theorem 8 also gives a conditional predecessor for simultaneous strong and rainbow completeness. Take the product of the injective hh-tuples on h+1h+1 colors and the surjective hh-tuples on h−1h-1 colors. The first relation can change an injection using a spare color. In the second, mark one position of each color. To move a mark to the vacant position, write its color there and release its old position. Swaps with the vacancy permute the marks arbitrarily. After placing them as prescribed, set the unmarked entry to its target value. Each move preserves surjectivity. The product reconfigures one factor at a time. Projecting onto the second factor and grouping its colors into two nonempty parts gives a map to NAE⁡h(2)\operatorname{NAE}^{(2)}_h. A coloring by the product gives exactly the two promised colorings. The proof of their Claim 34 decodes from a single edge-free set of measure at least 1/d1/d for the fixed target palette dd [6].

For linearly ordered triples, Filakovský, Nakajima, Opršal, Tasinato, and Wagner proved hardness from three colors to four [17]. Krokhin and Vagnozzi proved hardness from two to three [30]. Nakajima and Živný’s palette reduction raises both palettes by one [34 Theorem 5.6]. Banakh et al. state the resulting adjacent-palette hardness for all c≥2c \ge2 as Theorem 9, citing the Krokhin–Vagnozzi preprint for the starting case. Their Corollary 10 gives all 3≤c≤d3 \le c \le d conditionally [6]. For uniformity at least four, Nakajima, Verwimp, Wrochna, and Živný proved hardness for all 3≤c≤d3 \le c \le d [33].

Label Cover and coordinate approximation

Write [n]={1,…,n}[n]=\{1,\ldots,n\}. All product metrics are sup metrics. Uniform measure on a real cube means product Lebesgue probability. Uniform measure on a product of circles means product Haar probability. Conditional expectations and L2L^2 norms below use these laws.

The source problem

A Label Cover instance has finite question sets U,VU,V, nonempty answer sets ΣL,ΣR\Sigma_L,\Sigma_R, and a nonempty explicit list CC of test occurrences. Each occurrence ee specifies a left question pep_e, a right question qeq_e, and a total map Pe:ΣL→ΣRP_e:\Sigma_L\to\Sigma_R. Its value is

val⁡(C)=max⁡ℓ:U→ΣL, r′:V→ΣRPr⁡e∈C{Pe(ℓ(pe))=r′(qe)}.\operatorname{val}(C)=\max_{\ell:U\to\Sigma_L,\ r':V\to\Sigma_R}\Pr_{e\in C}\{P_e(\ell(p_e))=r'(q_e)\}.

The law on occurrences is uniform. Occurrences with the same pair of questions may have different projections.

Theorem 2.1 (Perfect-completeness Label Cover). For every fixed rational 0<σ<10<\sigma<1, there are fixed finite answer sets and a deterministic polynomial-time reduction from 3SAT to explicit Label Cover instances as above. Satisfiable formulas have value one. Unsatisfiable formulas have value at most σ\sigma.

This is the projection-game form of the PCP theorem with parallel repetition [2, 36]. A constant gap is amplified with a fixed number of repetitions chosen for σ\sigma. A product of uniform occurrence lists is again an explicit uniform occurrence list, and product projections are total. Perfect completeness is preserved at each repetition. See also the quantitative treatment of Dinur and Steurer and the total-projection formulation of Dinur, Khot, Kindler, Minzer, and Safra [16, 13]. The questions unused by all occurrences can be discarded. No regularity or bound on projection fibers will enter the proof.

Two bounds on coordinate influences

We use the following consequence of Austin’s junta theorem. For every L<∞L<\infty with L≥0L\ge0 and every τ>0\tau>0, there is an integer J(L,τ)≥1J(L,\tau)\ge1 with the following property. For any nn and any LL-Lipschitz G:[0,1]n→[−1,1]G:[0,1]^n\to[-1,1], there is a coordinate set SS, ∣S∣≤J(L,τ)|S|\le J(L,\tau), such that

∥G−E[G∣xS]∥2<τ.\lVert G-\mathbb{E}[G\mid x_S]\rVert_2<\tau.

Indeed, apply Austin’s Theorem 1.1 to the uniform interval with modulus t↦Ltt\mapsto Lt. Take the L1L^1 error below τ2/2\tau^2/2. The pointwise difference has absolute value at most two, giving the stated L2L^2 bound [3]. The quotient map from the cube to the product of circles preserves uniform probability and is nonexpanding. The same approximation therefore holds on a product of circles. A function of the selected coordinates will be called a junta.

For H∈L2(Tn)H\in L^2(\mathbb{T}^n), let EiE_i average coordinate ii while retaining all others. Set

Qi=1−Ei,Di(H)=∥QiH∥2.Q_i=1-E_i,\qquad D_i(H)=\lVert Q_iH\rVert_2.

Both EiE_i and QiQ_i are orthogonal projections. In particular, changing a function by η\eta in L2L^2 changes DiD_i by at most η\eta.

Lemma 2.2 (Influence detection and count). For every L<∞L < \infty, L≥0L \ge0, and ε>0\varepsilon> 0, there are β>0\beta> 0 and K≥1K \ge1 independent of nn such that every LL-Lipschitz H:Tn→[−1,1]H : \mathbb{T}^{n} \to[-1,1] satisfies

EH=0,EH2>ε⟹Di(H)≥β for some i,#{i:Di(H)≥β/2}≤K.\begin{aligned} \mathbb{E}H = 0,\quad\mathbb{E}H^{2} > \varepsilon&\quad\Longrightarrow\quad D_i(H) \ge\beta\text{ for some } i,\\ \#\{i : D_i(H) \ge\beta/2\} &\le K. \end{aligned}

Proof. Set J0=J(L,ε/2)J_0 = J(L,\sqrt{\varepsilon}/2). Choose a set SS of at most J0J_0 coordinates so that G=E[H∣zS]G = \mathbb{E}[H \mid z_S] satisfies ∥H−G∥2<ε/2\lVert H-G\rVert_2 < \sqrt{\varepsilon}/2. If HH has mean zero and ∥H∥2>ε\lVert H\rVert_2 > \sqrt{\varepsilon}, then GG has mean zero and ∥G∥2>ε/2\lVert G\rVert_2 > \sqrt{\varepsilon}/2.

To bound this last norm, expand HH using the commuting projections Ei,QiE_i,Q_i. For A⊆[n]A \subseteq[n], put

HA=(∏i∈AQi)(∏i∉AEi)H.H_A = \left(\prod_{i\in A} Q_i\right)\left(\prod_{i\notin A} E_i\right)H.

Their sum is HH, since Qi+Ei=1Q_i + E_i = 1. Two distinct summands are orthogonal by averaging at a coordinate in their symmetric difference. Conditioning on zSz_S retains exactly the summands with A⊆SA \subseteq S. The constant summand vanishes. Consequently

ε4<∥G∥22=∑∅≠A⊆S∥HA∥22≤∑i∈S∑A∋i∥HA∥22=∑i∈SDi(H)2.\frac{\varepsilon}{4} < \lVert G\rVert_2^2 = \sum_{\varnothing\ne A\subseteq S}\lVert H_A\rVert_2^2 \le\sum_{i\in S}\sum_{A\ni i}\lVert H_A\rVert_2^2 = \sum_{i\in S}D_i(H)^2.

Take β=ε/(4J0)\beta= \sqrt{\varepsilon/(4J_0)}.

For the count, approximate HH to error less than β/2\beta/2 by a junta G′G' on at most K=J(L,β/2)K = J(L,\beta/2) coordinates. Outside its coordinate set QiG′=0Q_iG' = 0, so Di(H)≤∥H−G′∥2<β/2D_i(H) \le\lVert H-G'\rVert_2 < \beta/2. This part holds for every mean.

The reduction

Fix the configuration and density in Theorem 1.1. The construction uses integers r≥s≥2r \ge s \ge2, m≥1m \ge1, and P≥1P \ge1. Take PP divisible by the denominators of all the offsets. Other finite data are a rational number 0<λ<10 < \lambda< 1 and a rational probability law μ\mu on ([r]s)\binom{[r]}{s}. The choices in § 8 fix all these data before the input formula is read. Put

D=mP,Γ=(D−1Z)/Z.D = mP,\qquad\Gamma= (D^{-1}\mathbb{Z})/\mathbb{Z}.

We describe the reduction on the output of Theorem 2.1.

A space of phase assignments

At layer i∈[r]i \in[r], form all question tuples and the corresponding answer set

q∈Vi−1×Ur−i,Mi=ΣRi−1×ΣLr−i.\mathbf{q} \in V^{i-1} \times U^{r-i},\qquad M_i = \Sigma_R^{i-1} \times\Sigma_L^{r-i}.

Both products have r−1r-1 positions. Occurrences of the same question at different positions remain separate positions. At adjacent layers ii, i+1i+1, take all pairs of question tuples that agree off position ii. For each occurrence between their questions at position ii, impose the map Mi→Mi+1M_i \to M_{i+1} applying its projection at that position and the identity elsewhere.

Place a separate copy of ΓMi\Gamma^{M_i} at each question tuple of layer ii. A grid point xx is an assignment of a phase xκx_\kappa to every answer κ\kappa of that tuple. Let X\mathcal{X} be the disjoint union of the grids. Define an undirected weighted link graph on X\mathcal{X}. Within a grid, link each pair with length its sup circle distance. For an imposed map π:Mi→Mi+1\pi: M_i \to M_{i+1}, link each point yy of its target grid to y∘πy \circ\pi of its source grid with length zero. The direction of this pullback is opposite to the answer map.

Let dist⁡\operatorname{dist} be shortest-path distance in the link graph, with value infinity between components. It is an extended pseudometric. Different grid points can have distance zero. For u∈Γu \in\Gamma, let Sux=x+u1S_u x = x + u\mathbf{1} in each grid. Within-grid lengths are translation invariant. On a projection link,

(Suy)∘π=Su(y∘π).(S_u y) \circ\pi= S_u(y \circ\pi).

Thus SuS_u and its inverse take links to links of the same length. Each SuS_u is an isometry of dist⁡\operatorname{dist}. We use the same notation for arbitrary diagonal translations on a continuous product torus.

Configuration tests

Choose an integer q≥hq \ge h with (h−1)/q<δ(h-1)/q < \delta. Denote by Kq(h)K_q^{(h)} the hypergraph of all hh-subsets of [q][q]. First test whether there exist w∈Xw \in\mathcal{X} and i<ji < j with

dist⁡(Suiw,Sujw)≤2ρ.(1)\operatorname{dist}(S_{u_i}w,S_{u_j}w) \le2\rho. \tag*{(1)}

If so, output Kq(h)K_q^{(h)} and stop. We call this the fallback. On the other branch, the closed balls of radius ρ\rho about the hh translates of any one center are pairwise disjoint.

The vertices on this branch will have locations xv∈Xx_v \in\mathcal{X}. Declare a set of hh distinct vertices to be an edge if it has an ordering v0,…,vh−1v_0,\ldots,v_{h-1} and a witness w∈Xw \in\mathcal{X} such that

dist⁡(xvj,Sujw)≤ρ(0≤j<h).(2)\operatorname{dist}(x_{v_j},S_{u_j}w) \le\rho\qquad(0 \le j < h). \tag*{(2)}

Both tests range over the entire grid union. In particular, ww need not be the location of an output vertex. The order in (2) is an existential witness for an unordered edge.

The law of a vertex

Sample r−1r-1 independent uniform occurrences e1,…,er−1e_1,\ldots,e_{r-1} from C\mathcal{C}. Write their questions as (pi,qi)(p_i,q_i). They determine the occurrence chain

qi=(q1,…,qi−1,pi,…,pr−1)(i∈[r]).\mathbf{q}_i=(q_1,\ldots,q_{i-1},p_i,\ldots,p_{r-1}) \qquad(i\in[r]).

For i≤ji\leq j, let πij:Mi→Mj\pi_{ij}:M_i\to M_j be the composite of the imposed maps along this chain. It acts at positions ii through j−1j-1. We use πii=id⁡\pi_{ii}=\operatorname{id} and πjkπij=πik\pi_{jk}\pi_{ij}=\pi_{ik}.

Independently sample B∼μB\sim\mu. In each layer j∈Bj\in B, draw a coefficient tjt_j independently from the law

Tm={0,1/m,…,1},Pr⁡(tj=k/m)=pk=λk∑v=0mλv.(3)\mathcal{T}_m=\{0,1/m,\ldots,1\},\qquad\Pr(t_j=k/m)=p_k=\frac{\lambda^k}{\sum_{v=0}^{m}\lambda^v}. \tag*{(3)}

Draw independent rotations θ^j,ℓ\widehat{\theta}_{j,\ell} uniformly from {0,1/P,…,(P−1)/P}\{0,1/P,\ldots,(P-1)/P\}, for j∈B,ℓ∈Mjj\in B,\ell\in M_j. These are real representatives in [0,1)[0,1). We multiply by the coefficient before reducing modulo one.

It will be useful to use the same formula on other layer sets and on real rotations. For nonempty I⊆[r]I\subseteq[r], c=min⁡Ic=\min I, define the phase vector

XI(t,θ)κ=∑j∈Itjθj,πcj(κ)(mod1),κ∈Mc.(4)X_I(t,\theta)_\kappa=\sum_{j\in I}t_j\theta_{j,\pi_{cj}(\kappa)}\pmod1,\qquad\kappa\in M_c. \tag*{(4)}

The location of the sampled outcome is XB(t,θ^)X_B(t,\widehat{\theta}) in the grid at qmin⁡B\mathbf{q}_{\min B}. Each summand has denominator dividing mPmP, so this is a point of the stated grid.

Proposition 3.1 (Deterministic encoding). For fixed parameters and alphabets the construction outputs a nonempty finite simple hh-uniform hypergraph in deterministic polynomial time. In the sampling branch a uniform vertex has exactly the law just specified, followed by a uniform choice among the copies of its outcome.

Proof. Let N=∣C∣≥1N=|\mathcal{C}|\geq1. Each of the Nr−1N^{r-1} occurrence chains has the same probability. Conditional on a chain, the probabilities of all remaining elementary outcomes are rational. Their denominators have a common multiple C0C_0 independent of the instance. Indeed, μ\mu, the coefficient table, and the possible numbers of rotation entries are fixed. For each conditional outcome of probability ww emit C0wC_0w distinct vertices with its location. The count is C0C_0 per chain and C0Nr−1C_0N^{r-1} overall. Uniform sampling now has the required law, including when distinct outcomes have the same location.

There are polynomially many question tuples and a constant number of grid points per tuple. Enumerate the links and multiply their lengths by DD. The weights are nonnegative integers at most DD. A minimum finite distance is realized on a simple path, so its integer representation has polynomial bit length. Exact all-pairs shortest paths give the comparisons in both tests. More explicitly, if ρ=p/n\rho=p/n and aa is a finite scaled distance, the tests are na≤2pDna\leq2pD and na≤pDna\leq pD, respectively. An infinite distance fails either comparison.

For the second test enumerate centers and ordered hh-tuples of distinct vertex indices. Store each successful edge once under its sorted indices. This costs O(h∣C∣∣V(H)∣h)O(h|\mathcal{C}|\lvert V(H)\rvert^h) comparisons after the distances are available. All loops here have polynomial total cost for fixed r,hr,h and alphabets.

There is even an edge in the sampling branch. Fix a chain and a BB of positive probability. Give its first layer coefficient one and the remaining layers coefficient zero. In the first block one may set all rotations equal to uju_j, for each jj, since their denominators divide PP. These hh positive-probability outcomes have distinct constant locations and witness an edge about the zero vector of that grid. The fallback also contains an edge. □\square

Completeness and circle colorings

Lemma 4.1 (Evaluation). A labeling satisfying every occurrence rules out the fallback and gives the phase map in Theorem 1.1.

Proof. For a question tuple q\mathbf{q}, let κq\kappa_{\mathbf{q}} be the product of its assigned answers. Define φ(x)=xκq\varphi(x)=x\kappa_{\mathbf{q}} on its grid. Evaluation is nonexpanding on within-grid links. If π\pi is an imposed map from q\mathbf{q} to q′\mathbf{q}', satisfaction gives π(κq)=κq′\pi(\kappa_{\mathbf{q}})=\kappa_{\mathbf{q}'}. Evaluations therefore agree across the corresponding zero links. Along any path, the circle distance between its endpoint evaluations is bounded by the sum of its link lengths. Hence

dT(φ(x),φ(y))≤dist⁡(x,y),φ(Sux)=φ(x)+u.d_{\mathbb{T}}(\varphi(x),\varphi(y))\leq\operatorname{dist}(x,y),\qquad\varphi(S_u x)=\varphi(x)+u.

At any ww, the distance between translates i,ji,j is at least dT(ui,uj)>2ρd_{\mathbb{T}}(u_i,u_j)>2\rho. This excludes (1). Give vertex vv the phase φ(xv)\varphi(x_v). For an edge with witness ww, nonexpansion in (2) gives the required inequalities with t=φ(w)t=\varphi(w). □

An antipodal pair

Use CgC_g on Z/gZ\mathbb{Z}/g\mathbb{Z} with edges of difference ±1\pm1. For two offsets 0,1/20,1/2, the two errors relative to a common translate give an error at most 2ρ2\rho in the displacement.

Lemma 4.2 (Odd-cycle rounding). Let g=2k+1≥3g=2k+1\geq3. Suppose a graph has a phase map under which the displacement on every edge has circle distance at most 1/(4g)1/(4g) from 1/21/2. Then the graph maps to CgC_g.

Proof. At a vertex with real phase lift uu, give the color

k−1⌊gu⌋(modg).k^{-1}\lfloor gu\rfloor\pmod g.

Here k−1=−2(modg)k^{-1}=-2\pmod g. Changing the lift adds a multiple of gg to the bin index. On an edge, choose the other lift vv so that

g(v−u)∈[k+1/4,k+3/4].g(v-u)\in[k+1/4,k+3/4].

Writing {gu}\{gu\} for the fractional part gives

⌊gv⌋−⌊gu⌋=⌊{gu}+g(v−u)⌋∈{k,k+1}.\lfloor gv\rfloor-\lfloor gu\rfloor=\lfloor\{gu\}+g(v-u)\rfloor\in\{k,k+1\}.

The interval includes its endpoints, and the floor assigns a boundary point to the bin starting there. Since k+1≡−k(modg)k+1\equiv-k\pmod g, the colors differ by 11 or −1-1. □

Remark 4.3. For g=3g=3, Open Mathematics Courses, Exercise 6.5, observes that the three-bin completeness argument works for any antipodal displacement cutoff strictly below 1/61/6 [12]. For the configuration theorem the displacement cutoff is twice the per-vertex radius. We use ρ=1/(8g)\rho=1/(8g).

A regular polygon

Lemma 4.4 (Two partitions of the circle). Use the offsets j/hj/h, 0≤j<h0\leq j<h, with h≥3h\geq3 and 0<ρ<1/(2h(h+1))0<\rho<1/(2h(h+1)). On every hypergraph satisfying the phase condition of Theorem 1.1, the partitions into h+1h+1 and h−1h-1 equal half-open bins give a strong and a rainbow coloring, respectively.

Proof. The distance between any two distinct ideal phases on an edge is at least 1/h1/h. The corresponding actual phases have distance at least 1/h−2ρ>1/(h+1)1/h - 2\rho> 1/(h+1). A bin of width 1/(h+1)1/(h+1) cannot contain two such points.

Choose a lift tt of the translation on an edge and write its lifts as t+j/h+ejt + j/h + e_j, with ∣ej∣≤ρ|e_j| \le\rho. Set eh=e0e_h = e_0 for the next copy of the first vertex. Every successive gap lies in

[1/h−2ρ,1/h+2ρ]⊂(0,1/(h−1)).[1/h - 2\rho, 1/h + 2\rho] \subset(0, 1/(h-1)).

The positive lower bound gives cyclic order, including the gap across the seam. If a lifted bin [a,a+1/(h−1))[a, a + 1/(h-1)) were empty, the last lift before aa would be strictly less than aa and the next would be at least a+1/(h−1)a + 1/(h-1). The gap bound excludes this. Both partitions use the original phase map on all vertices.

A path of legal tuples

Lemma 4.5 (Circle coloring for a relation). Suppose a symmetric relation R⊆ChR \subseteq C^h contains a=(a0,…,ah−1)a = (a_0, \ldots, a_{h-1}) and a single-coordinate path in RR from aa to (a1,…,ah−1,a0)(a_1, \ldots, a_{h-1}, a_0). There are a rational 0<ρ∗<1/(2h)0 < \rho_* < 1/(2h) and a map χ:T→C\chi: \mathbb{T} \to C such that

(χ(t+j/h+ej))0≤j<h∈Rwhenever t∈T,∣ej∣≤ρ∗.\left(\chi(t + j/h + e_j)\right)_{0 \leq j < h} \in R \quad\text{whenever } t \in\mathbb{T},\quad|e_j| \leq\rho_*.

Every nonempty symmetric reconfigurable relation has this property.

Proof. Write the path as a0,…,ama^0, \ldots, a^m. Schedule its steps at distinct increasing interior times of [0,1/h)[0, 1/h). Let W(t)W(t) be the current tuple, using the new value at a step. It equals a0a^0 near zero and ama^m near 1/h1/h. Extend it to the real line by

Wj(t+1/h)=Wj+1(t)(jmodh).(5)W_j(t + 1/h) = W_{j+1}(t) \qquad(j \mathbin{\mathrm{mod}} h). \tag*{(5)}

At the seam 1/h1/h, the new value of entry jj is aj+10=ajma^0_{j+1} = a^m_j, its value on the left. Rotation gives the same equality at every seam. After hh intervals each entry returns to its original position. The extension is periodic with period one. Set χ(t)=W0(t)\chi(t) = W_0(t). Then χ(t+j/h)=Wj(t)\chi(t + j/h) = W_j(t).

If there are steps, their times repeat with period 1/h1/h. Choose 2ρ∗2\rho_* smaller than 1/h1/h and smaller than the minimum spacing of successive step times, including the spacing across a seam. A rational choice exists. With no steps, just take 2ρ∗<1/h2\rho_* < 1/h. A closed interval [t−ρ∗,t+ρ∗][t - \rho_*, t + \rho_*] meets at most one step. If it meets one, the tuples on its two sides belong to RR by symmetry and differ in one coordinate. Sampling entry jj at an arbitrary t+ejt + e_j therefore produces one of these two tuples. This includes sampling exactly at the step. If the interval meets none, it gives W(t)W(t). Equation (5) identifies the sampled entries with χ(t+j/h+ej)\chi(t + j/h + e_j). Finally, symmetry puts the rotation of any a∈Ra \in R in RR, and reconfigurability supplies the path.

Lemma 4.6 (Merging colors on triples). A strong four-coloring of a 3-uniform hypergraph gives an LO3\mathrm{LO}_3-coloring.

Proof. Send 0, 1, 2, 3, respectively, to 0, 0, 1, 2. A triple containing strong color 3 has a unique maximum of 2. A triple omitting it has strong colors 0, 1, 2 and a unique maximum of 1.

Soundness I. From an independent set to lists

The soundness framework of OpenAI [26] turns functions on tuple tori into lists of Label Cover answers and tests their coordinate influences. We give the argument for configuration edges, using diagonal integration and lists for subchains of one fixed size.

Fix the Label Cover instance and a nonempty independent set A\mathcal{A} in the sampling branch. The choice of A\mathcal{A} precedes every random choice in the analysis. Its set of locations is A={xv:v∈A}⊆X\mathcal{A}=\{x_v:v\in\mathcal{A}\}\subseteq\mathcal{X}. The vertex set retains multiplicities throughout. Only A\mathcal{A} forgets them.

A function with zero integral on each diagonal circle

Lemma 5.1 (Translated bump). Put L=2/ρL=2/\rho. There is a function f:X→[−1,1]f:\mathcal{X}\to[-1,1] constant on zero links such that f(x)≥1/hf(x)\ge1/h for every x∈Ax\in\mathcal{A}. On the grid at each tuple q\mathbf{q} it has an LL-Lipschitz extension Fq:TMi→[−1,1]F_{\mathbf{q}}:\mathbb{T}^{M_i}\to[-1,1] satisfying

∫TFq(Svy) dv=0(y∈TMi).(6)\int_{\mathbb{T}} F_{\mathbf{q}}(S_v y)\,dv=0 \qquad(y\in\mathbb{T}^{M_i}). \tag*{(6)}

Along any chain, write Fi=FqiF_i=F_{\mathbf{q}_i}. For i≤ji\le j,

∣Fi(y∘πij)−Fj(y)∣≤2L/D(y∈TMj).(7)\left|F_i(y\circ\pi_{ij})-F_j(y)\right|\le2L/D \qquad(y\in\mathbb{T}^{M_j}). \tag*{(7)}

Proof. On the whole grid union define

b(x)=(1−dist⁡(x,A)ρ)+,f(x)=b(x)−1h∑j=0h−1b(Sujx).b(x)=\left(1-\frac{\operatorname{dist}(x,\mathcal{A})}{\rho}\right)_{+}, \qquad f(x)=b(x)-\frac{1}{h}\sum_{j=0}^{h-1}b(S_{u_j}x).

Take b=0b=0 at infinite distance. Suppose x∈Ax\in\mathcal{A} and every summand b(Sujx)b(S_{u_j}x) is positive. For each jj, choose yj∈Ay_j\in\mathcal{A} with dist⁡(yj,Sujx)<ρ\operatorname{dist}(y_j,S_{u_j}x)<\rho. Failure of (1) makes the closed radius-ρ\rho balls at this center disjoint. Thus the yjy_j are distinct. Choose one selected vertex at each. These hh vertices form an edge by (2) with w=xw=x. This contradicts independence. At least one summand is zero. Since b(x)=1b(x)=1 and the other summands are at most one, f(x)≥1/hf(x)\ge1/h.

On a component meeting A\mathcal{A}, distance to A\mathcal{A} is 1-Lipschitz for the path pseudometric. On a component disjoint from A\mathcal{A}, bb is constant. A within-grid link bounds path distance from above by sup circle distance. It follows that bb restricted to a grid is 1/ρ1/\rho-Lipschitz. Points at zero distance have equal values under bb, as do their simultaneous translates. Hence ff agrees across zero links.

At the tuple q\mathbf{q}, extend the bump by the McShane formula and clip to the interval [0,1][0,1] [32]. Explicitly, with GqG_{\mathbf{q}} denoting this tuple’s grid, let

Bq(y)=min⁡{1,min⁡x∈Gq(b(x)+ρ−1d∞(x,y))}.B_{\mathbf{q}}(y)=\min\left\{1,\min_{x\in G_{\mathbf{q}}}\left(b(x)+\rho^{-1}d_{\infty}(x,y)\right)\right\}.

Every term is nonnegative. The inner minimum is 1/ρ1/\rho-Lipschitz. At a grid point yy, every term is at least b(y)b(y) and the term x=yx=y gives equality. The outer minimum preserves this value and the Lipschitz bound. Now put

Fq(y)=Bq(y)−1h∑j=0h−1Bq(Sujy).F_{\mathbf{q}}(y)=B_{\mathbf{q}}(y)-\frac{1}{h}\sum_{j=0}^{h-1}B_{\mathbf{q}}(S_{u_j}y).

Every required shift preserves the grid, so FqF_{\mathbf{q}} extends ff. Its two terms take values in [0,1][0,1] and each has Lipschitz constant at most 1/ρ1/\rho. On the diagonal circle SvyS_vy, the integral of each translated bump equals the integral of the first bump by v↦v+ujv\mapsto v+u_j. This gives (6) at every yy.

Finally, round y∈TMjy\in\mathbb{T}^{M_j} to a grid point y′y' at sup distance at most 1/D1/D. Pullback preserves this upper bound. The grid points y′y' and y′∘πijy'\circ\pi_{ij} are joined by a sequence of zero links, so ff agrees at the two endpoints. The two rounding errors give (7), independently of the length of the composite. □\square

Lists on a subchain

The only subchains that will need lists have s−1s-1 layers. They are the possible results of deleting one layer from a sampled ss-set. Fix γ>0\gamma> 0. For I∈([r]s−1)I \in\binom{[r]}{s-1} and a fixed coefficient vector t∈TmIt \in\mathcal{T}^{I}_{m}, consider

GI,t(θ)=Fmin⁡I(XI(t,θ)),θ∈∏j∈I[0,1]Mj.(8)G_{I,t}(\theta)=F_{\min I}(X_I(t,\theta)),\qquad\theta\in\prod_{j\in I}[0,1]^{M_j}. \tag*{(8)}

The rotation entries now have continuous product law. In one coordinate of XIX_I, each block contributes one scalar multiplied by a number in [0,1][0,1]. Hence changing the whole rotation array by sup distance η\eta changes the phase vector by at most (s−1)η(s-1)\eta in circle sup distance. This holds for all projection maps, including those with large fibers. The function GI,tG_{I,t} is therefore (s−1)L(s-1)L-Lipschitz.

Lemma 5.2 (Local choice of lists). For each fixed chain and each I∈([r]s−1)I \in\binom{[r]}{s-1}, there are sets SIj⊆MjS^j_I \subseteq M_j, j∈Ij \in I, with

∑j∈I∣SIj∣≤d,d=J((s−1)L,γ)(m+1)s−1.(9)\sum_{j\in I}|S^j_I|\le d,\qquad d=J((s-1)L,\gamma)(m+1)^{s-1}. \tag*{(9)}

For every t∈TmIt \in\mathcal{T}^{I}_{m} there is a junta gI,tg_{I,t} on entries (j,ℓ)(j,\ell) with ℓ∈SIj\ell\in S^j_I such that ∥GI,t−gI,t∥2<γ\|G_{I,t}-g_{I,t}\|_2<\gamma. The lists depend only on the tuples in II, their fixed functions, and the projections between them.

Proof. Apply the junta bound of § 2 to (8) at every coefficient vector. Order the scalar coordinates once and for all. Among the sets of size at most J((s−1)L,γ)J((s-1)L,\gamma) whose coordinate conditional expectation has error less than γ\gamma, choose the first in a fixed ordering. Use that conditional expectation as gI,tg_{I,t}. Union the chosen indices within each block over the (m+1)s−1(m+1)^{s-1} vectors tt. This proves the bound and the simultaneous approximation. The choice rule uses only the data defining (8). It is part of the analysis and need not be run by the reduction.

Project the lists to the answer set at the last layer:

AI=⋃j∈Iπjr(SIj)⊆Mr.(10)A_I=\bigcup_{j\in I}\pi_{jr}(S^j_I)\subseteq M_r. \tag*{(10)}

Each AIA_I has size at most dd. The projection in this formula can use occurrences outside II. We decode from the selected coordinates before this terminal projection.

Lemma 5.3 (Decoding separated lists). If val⁡(C)≤σ\operatorname{val}(\mathcal{C})\le\sigma and I,J∈([r]s−1)I,J\in\binom{[r]}{s-1} satisfy max⁡I<min⁡J\max I<\min J, then

Pr⁡chain(AI∩AJ≠∅)≤d2σ.\Pr_{\mathrm{chain}}(A_I\cap A_J\ne\varnothing)\le d^2\sigma.

Proof. Put k=max⁡Ik=\max I, and condition on all occurrences except eke_k. Each tuple in II has left question pkp_k at position kk. Its remaining entries are fixed. All projections internal to that subchain use occurrences with indices below kk. The left list rule consequently depends on eke_k only through pkp_k. On JJ, position kk already has right question qkq_k and all internal projections avoid eke_k. Its list rule depends on eke_k only through qkq_k. The family of functions FqF_q was fixed for the entire instance in Lemma 5.1. Looking up a function at a tuple respects these dependencies even for different occurrences with the same own question.

On each side collect the entries at position kk of all its selected answers. This gives at most dd left candidates as a function of the left question and at most dd right candidates as a function of the right question. Order and pad the lists to length dd with arbitrary answers, allowing an initially empty list. For each pair of list indices, reading those entries at all own questions defines one labeling of the original instance. If the terminal lists intersect, two selected product answers have equal terminal images. At position kk, the left answer was acted on by exactly PekP_{e_k}, and the right answer was unchanged. Thus one of the d2d^2 labelings satisfies eke_k. Conditional on the background this occurrence still has its original uniform law. Each labeling satisfies it with probability at most σ\sigma. A union bound and then averaging over the background prove the claim.

Soundness II. Finite distributional alignment

For B∈([r]s)B \in\binom{[r]}{s} we seek a map a:Mr→Ba : M_r \to B such that

a(AB∖{i})⊆B∖{i}(i∈B).(11)a(A_{B\setminus\{i\}}) \subseteq B \setminus\{i\} \qquad(i \in B). \tag*{(11)}

In fact, (11) is equivalent to the absence of a label common to all ss deletion lists. For each label, one may assign any index whose deletion list omits it. Disjointness on separated subchains does not itself give this condition on a prescribed BB. For example, with s=3s=3 the same label can occur on all three pairs of a triple without occurring on two separated pairs. The distribution in the next lemma works for every list family.

Lemma 6.1 (Distributional alignment for deletions). For integers s≥2s \ge2, d≥1d \ge1 and every η>0\eta> 0, there exist r≥sr \ge s and a rational probability law μ\mu on ([r]s)\binom{[r]}{s} with the following property. Let MM be any set. For every I∈([r]s−1)I \in\binom{[r]}{s-1} give a list AI⊆MA_I \subseteq M of size at most dd. Assume

AI∩AJ=∅if max⁡I<min⁡J.A_I \cap A_J = \varnothing\quad\text{if } \max I < \min J.

With probability at least 1−η1-\eta over B∼μB \sim\mu, a map a:M→Ba : M \to B satisfying (11) exists.

Proof. We may assume 0<η<10 < \eta< 1 by decreasing it. Order the entries in each list. A pattern consists of the occupied slots in these ordered lists and the equivalence relation recording equality of their labels. For a fixed rr the number of allowed patterns is finite. Patterns can be realized using their equivalence classes as labels. Both the hypothesis and the desired conclusion depend only on the pattern.

For a fixed pattern and an appearing label xx, define an index

p(x)=max⁡{min⁡I:x∈AI}.p(x) = \max\{\min I : x \in A_I\}.

Every occurrence x∈AIx \in A_I satisfies

min⁡I≤p(x)≤max⁡I.(12)\min I \le p(x) \le\max I. \tag*{(12)}

The lower bound follows from the definition. If the upper bound failed, a list attaining the maximum would be strictly to the right of II and would share xx with it. This proves the upper bound. We will round this one index in the same way for every occurrence of xx.

A good set for any distribution of patterns. Choose an integer nn with sd/n<η/4sd/n < \eta/4. By the finite Ramsey theorem take rr large enough that every coloring of the ss-subsets of [r][r] in at most (n+1)sd(n+1)^{sd} colors has a homogeneous set of size 2s−12s-1 [35]. This choice precedes the distribution of patterns.

Now give the allowed patterns any probability distribution ν\nu. For an ss-set U={v1<⋯<vs}U=\{v_1<\cdots<v_s\}, form sdsd numbers, one for each j∈[s]j \in[s] and b∈[d]b \in[d]. With I=U∖{vj}I=U\setminus\{v_j\}, the number is

Pr⁡ν{slot b of AI is occupied by x with p(x)≤vj}.(13)\Pr\nolimits_{\nu}\{\text{slot }b\text{ of }A_I\text{ is occupied by }x\text{ with }p(x)\le v_j\}. \tag*{(13)}

Here p(x)p(x) is computed on the whole pattern on [r][r]. Color UU by the vector of the integer parts of nn times these numbers. There are at most (n+1)sd(n+1)^{sd} colors.

In a homogeneous set of size 2s−12s-1, write the points in order as

b1<c1<b2<c2<⋯<cs−1<bs,B={b1,…,bs}.b_1 < c_1 < b_2 < c_2 < \cdots< c_{s-1} < b_s,\qquad B=\{b_1,\ldots,b_s\}.

Use c1,…,cs−1c_1,\ldots,c_{s-1} as boundaries. Round pp to bjb_j when cj−1<p≤cjc_{j-1}<p\le c_j, with c0=−∞c_0=-\infty, cs=+∞c_s=+\infty. For each pattern, assign every appearing label by this rounding and send absent labels anywhere in BB. Consider I=B∖{bj}I = B \setminus\{b_j\}. If j=1j = 1 or ss, (12) prevents any label of AIA_I from rounding to bjb_j. For 1<j<s1 < j < s, the two points cj−1,cjc_{j-1}, c_j occupy the same rank when inserted separately into II. The ss-sets I∪{cj−1}I \cup\{c_{j-1}\} and I∪{cj}I \cup\{c_j\} have the same Ramsey color. For any fixed slot of AIA_I, subtract its probabilities in (13) at the two thresholds. Both events concern the very same slot in the same random pattern, and the first event is contained in the second. Their difference is exactly the probability that the slot is occupied and its label rounds to bjb_j. Homogeneity bounds this difference by 1/n1/n. A union bound over ss deletions and at most dd slots gives

Pr⁡ν{B admits no assignment}≤sd/n<η/4.(14)\Pr_{\nu}\{B\text{ admits no assignment}\} \le sd/n < \eta/4. \tag*{(14)}

The set BB here may depend on ν\nu.

One rational law for all patterns. Let N0N_0 be the number of allowed patterns. Start each at weight one. At each round, normalize the current weights to a probability law and choose a set BB by (14). Double the weight of every pattern for which that set admits no assignment. The total weight increases by a factor at most 1+η/41 + \eta/4. If a particular pattern fails in mCm_C of TT rounds, its own weight is 2mC2^{m_C}. It follows that

mCT≤log⁡N0Tlog⁡2+log⁡(1+η/4)log⁡2.\frac{m_C}{T} \le\frac{\log N_0}{T\log2} + \frac{\log(1+\eta/4)}{\log2}.

The second term is less than η/2\eta/2. Choose TT to make the first term less than η/2\eta/2. Give each of the TT chosen sets mass 1/T1/T, adding masses for repetitions. This rational law has failure probability less than η\eta for every pattern. Every actual list family induces such a pattern, and assignments transfer back to its labels.

Call a chain and BB aligned when (11) holds for their terminal lists. Apply Lemma 6.1 with η=ε\eta= \varepsilon. For a chain whose separated lists are all disjoint, the conditional failure probability over BB is at most ε\varepsilon. There are at most 4r4^r ordered pairs of subsets of [r][r]. Lemma 5.3 and the union bound give

Pr⁡chain,B{unaligned}≤4rd2σ+ε.(15)\Pr_{\mathrm{chain},B}\{\text{unaligned}\} \le4^r d^2\sigma+ \varepsilon. \tag*{(15)}

The order of the choices matters here. The single law μ\mu belongs to the reduction. The lists belong to the independent set. An assignment for an aligned pair can be fixed before sampling any coefficients or rotations.

Soundness III. The coefficient test

Fix an aligned chain and BB, and choose an assignment a:Mr→Ba : M_r \to B as in (11). Put b=min⁡Bb = \min B. Write θ\theta for independent uniform real rotation entries in [0,1)[0,1). Let z=(zi)i∈Bz = (z_i)_{i\in B} consist of independent Haar phases, independent of all rotations and coefficients. Define

Y(t,θ,z)κ=za(πbr(κ))+XB(t,θ)κ(mod1),κ∈Mb,H(t,θ;z)=Fb(Y(t,θ,z)).(16)\begin{aligned} Y(t,\theta,z)_\kappa&= z_{a(\pi_{b r}(\kappa))} + X_B(t,\theta)_\kappa\pmod1,\qquad\kappa\in M_b,\\ H(t,\theta;z) &= F_b\bigl(Y(t,\theta,z)\bigr). \tag*{(16)} \end{aligned}

The auxiliary phase depends on the terminal answer. Thus coordinates in different grids whose answers have the same terminal image will read the same auxiliary phase.

Lemma 7.1 (Conditional mean zero). For every fixed t,θt,\theta, the function z↦H(t,θ;z)z\mapsto H(t,\theta;z) is LL-Lipschitz, has absolute value at most one, and satisfies EzH(t,θ;z)=0\mathbb{E}_z H(t,\theta;z)=0.

Proof. Each coordinate of YY reads one ziz_i with coefficient one. Thus YY is nonexpanding in zz and Y(t,θ,z+v1)=SvY(t,θ,z)Y(t,\theta,z+v\mathbf{1})=S_vY(t,\theta,z). With t,θt,\theta fixed, Haar invariance and (6) give

EzH(t,θ;z)=∫TEzFb(Y(t,θ,z+v1)) dv=Ez∫TFb(SvY(t,θ,z)) dv=0.\mathbb{E}_z H(t,\theta;z) = \int_{\mathbb{T}} \mathbb{E}_z F_b\bigl(Y(t,\theta,z+v\mathbf{1})\bigr)\,dv = \mathbb{E}_z \int_{\mathbb{T}} F_b\bigl(S_vY(t,\theta,z)\bigr)\,dv = 0.

The range and Lipschitz bounds follow from those of FbF_b. The identity also covers the all-zero coefficient vector.

Take β,K\beta,K from Lemma 2.2 at L,εL,\varepsilon. In this section assume

Lm<β2,λK<ε,(1−pm)s<ε,\frac{L}{m}<\frac{\beta}{2},\qquad\lambda K<\varepsilon,\qquad(1-p_m)^s<\varepsilon,
s(2γ)2β2<ε,2LD<γ,2LsP<ε.(17)\frac{s(2\gamma)^2}{\beta^2}<\varepsilon,\qquad\frac{2L}{D}<\gamma,\qquad\frac{2Ls}{P}<\varepsilon. \tag*{(17)}

For fixed t,θt,\theta, let

V(t,θ)=EzH(t,θ;z)2,Di(t,θ)=∥QiH(t,θ;⋅)∥L2(z).V(t,\theta)=\mathbb{E}_z H(t,\theta;z)^2,\qquad D_i(t,\theta)=\lVert Q_iH(t,\theta;\cdot)\rVert_{L^2(z)}.

Applying Lemma 2.2 pointwise in t,θt,\theta gives

V(t,θ)>ε⟹Di(t,θ)≥β for some i∈B,(18)V(t,\theta)>\varepsilon\quad\Longrightarrow\quad D_i(t,\theta)\ge\beta\ \text{for some }i\in B, \tag*{(18)}
#{i∈B:Di(t,θ)≥β/2}≤K.(19)\#\{i\in B:D_i(t,\theta)\ge\beta/2\}\le K. \tag*{(19)}

The count holds for all coefficient vectors. Its bound was fixed independently of ss.

Deleting a zero coefficient

Call a coefficient full when it equals one and let F\mathcal{F} be the event that at least one coefficient is full. By independence, Pr⁡(Fc)=(1−pm)s\Pr(\mathcal{F}^{c})=(1-p_m)^s.

Lemma 7.2. Fix t∈Ft\in\mathcal{F} and i∈Bi\in B with ti=0t_i=0. Then

EθDi(t,θ)2<(2γ)2.\mathbb{E}_{\theta}D_i(t,\theta)^2<(2\gamma)^2.

Proof. Choose j∈Bj\in B with tj=1t_j=1. Then j≠ij\ne i. Put I=B∖{i}I=B\setminus\{i\} and c=min⁡Ic=\min I. In the rotation array on II, modify only block jj by setting

θj,ℓ′={θj,ℓ+za(πjr(ℓ))},ℓ∈Mj.(20)\theta'_{j,\ell}=\{\theta_{j,\ell}+z_{a(\pi_{j r}(\ell))}\},\qquad\ell\in M_j. \tag*{(20)}

Here braces mean the representative in [0,1)[0,1) of a sum modulo one. Conditional on zz, these are fixed translations of the individual uniform coordinates. The joint rotation law remains product uniform, including when several entries receive the same shift.

Let y=XI(t∣I,θ′)y=X_I(t|_I,\theta'). Composition of the projections gives for every κ∈Mb\kappa\in M_b

yπbc(κ)=Y(t,θ,z)κ.y_{\pi_{bc}(\kappa)}=Y(t,\theta,z)_\kappa.

Indeed, the deleted term has coefficient zero. In the translated block, the added phase is za(πjrπbj(κ))=za(πbr(κ))z_a(\pi_{jr}\pi_{bj}(\kappa))=z_a(\pi_{br}(\kappa)). The integer removed by taking the representative in (20) disappears in the phase sum because tj=1t_j=1. Consequently (7) gives the pointwise bound

∣H(t,θ;z)−GI,t∣I(θ′)∣=∣Fb(y∘πbc)−Fc(y)∣≤2L/D<γ.\left|H(t,\theta;z)-G_{I,t|_I}(\theta')\right|=\left|F_b(y\circ\pi_{bc})-F_c(y)\right|\leq2L/D<\gamma.

This also treats deletion of the minimum of BB.

Take the junta gI,t∣Ig_{I,t|_I} from Lemma 5.2. Preservation of the rotation law at every fixed zz gives

∥GI,t∣I(θ′)−gI,t∣I(θ′)∥L2(θ,z)<γ.\left\|G_{I,t|_I}(\theta')-g_{I,t|_I}(\theta')\right\|_{L^2(\theta,z)}<\gamma.

Only entries in block jj can introduce dependence on zz into this junta. Each such selected entry ℓ\ell has πjr(ℓ)∈AI\pi_{jr}(\ell)\in A_I, hence a(πjr(ℓ))∈Ia(\pi_{jr}(\ell))\in I by alignment. Therefore gI,t∣I(θ′)g_{I,t|_I}(\theta') is independent of ziz_i. Apply QiQ_i, acting on ziz_i in the joint product space. It kills this junta and has norm at most one. We obtain

(EθDi(t,θ)2)1/2=∥QiH∥L2(θ,z)≤∥H−gI,t∣I(θ′)∥L2(θ,z)<2γ.\left(\mathbb{E}_{\theta}D_i(t,\theta)^2\right)^{1/2}=\left\|Q_iH\right\|_{L^2(\theta,z)}\leq\left\|H-g_{I,t|_I}(\theta')\right\|_{L^2(\theta,z)}<2\gamma.

For each fixed t∈Ft\in\mathcal{F}, Markov’s inequality and a union bound over its zero coefficients now apply. After averaging in tt,

Pr⁡{F, ∃i∈B:ti=0, Di(t,θ)≥β}≤s(2γ)2/β2<ε.(21)\Pr\{\mathcal{F},\ \exists i\in B:t_i=0,\ D_i(t,\theta)\geq\beta\}\leq s(2\gamma)^2/\beta^2<\varepsilon. \tag*{(21)}

Lowering a positive coefficient

Lemma 7.3. Under the product laws on t,θt,\theta,

Pr⁡{∃i∈B:ti>0, Di(t,θ)≥β}≤λK.\Pr\{\exists i\in B:t_i>0,\ D_i(t,\theta)\geq\beta\}\leq\lambda K.

Proof. Fix ii, the array θ\theta, and the other coefficients. At level ti=k/mt_i=k/m, denote H(t,θ;⋅)H(t,\theta;\cdot) by HkH_k and its ii-influence by dkd_k. Moving down one level changes each phase coordinate by distance at most 1/m1/m, since each rotation is in [0,1)[0,1). Hence

∣dk−dk−1∣≤∥Qi(Hk−Hk−1)∥2≤L/m<β/2(1≤k≤m).|d_k-d_{k-1}|\leq\left\|Q_i(H_k-H_{k-1})\right\|_2\leq L/m<\beta/2\qquad(1\leq k\leq m).

If dk≥βd_k\geq\beta, the preceding level has dk−1≥β/2d_{k-1}\geq\beta/2. Its probability is pk−1=pk/λp_{k-1}=p_k/\lambda. It follows that

∑k=1mpk1{dk≥β}≤λ∑k=0m−1pk1{dk≥β/2}≤λ∑k=0mpk1{dk≥β/2}.\sum_{k=1}^{m}p_k\mathbf{1}_{\{d_k\geq\beta\}}\leq\lambda\sum_{k=0}^{m-1}p_k\mathbf{1}_{\{d_k\geq\beta/2\}}\leq\lambda\sum_{k=0}^{m}p_k\mathbf{1}_{\{d_k\geq\beta/2\}}.

Average over the fixed data, use the union bound over ii, and apply (19). The right side becomes at most λE#{i:Di(t,θ)≥β/2}≤λK\lambda\mathbb{E}\#\{i:D_i(t,\theta)\geq\beta/2\}\leq\lambda K. Lowering the only full coefficient is allowed because (19) holds at the resulting vector as well.

Absorption and the discrete law

Proposition 7.4 (Mean square on an aligned pair). Under (17), for every aligned chain and BB,

Et,θ^Fb(XB(t,θ^))2<6ε.\mathbb{E}_{t,\hat{\theta}}F_b\left(X_B(t,\hat{\theta})\right)^2 < 6\varepsilon.

Proof. By (18), if V(t,θ)>εV(t,\theta)>\varepsilon, then one of three events occurs. There is no full coefficient, a zero coefficient is influential in the presence of a full one, or a positive coefficient is influential. Their probabilities are bounded by (1−pm)(1-p_m), s(2γ)2/β2s(2\gamma)^2/\beta^2, and λK\lambda K, respectively, by (21) and Lemma 7.3. All three are less than ε\varepsilon. Since 0≤V≤10\leq V\leq1,

Et,θ,zH(t,θ;z)2=Et,θV(t,θ)≤ε+Pr⁡{V>ε}<4ε.(22)\mathbb{E}_{t,\theta,z}H(t,\theta;z)^2=\mathbb{E}_{t,\theta}V(t,\theta)\leq\varepsilon+\Pr\{V>\varepsilon\}<4\varepsilon. \tag*{(22)}

To remove zz, fix t∈Ft\in\mathcal{F} and choose any one full block jj. Translate its rotations by (20), now retaining all blocks. The same coordinate computation gives XB(t,θ′)=Y(t,θ,z)X_B(t,\theta')=Y(t,\theta,z). The conditional rotation law is unchanged for each zz, so

Eθ,zH(t,θ;z)2=EθFb(XB(t,θ))2(t∈F).\mathbb{E}_{\theta,z}H(t,\theta;z)^2=\mathbb{E}_{\theta}F_b\left(X_B(t,\theta)\right)^2 \qquad(t\in\mathcal{F}).

Multiply by the probability of each such tt and sum. The resulting contribution to the unshifted square is below 4ε4\varepsilon by (22). On Fc\mathcal{F}^{c} the square is at most one, which adds less than ε\varepsilon.

Finally couple the discrete rotations by θ^j,ℓ=⌊Pθj,ℓ⌋/P\hat{\theta}_{j,\ell}=\lfloor P\theta_{j,\ell}\rfloor/P. They have exactly the independent uniform law of the construction. Each phase coordinate in (4) moves by at most s/Ps/P. Since ∣Fb∣≤1|F_b|\leq1, the difference of the two squared function values is at most

2Ld∞(XB(t,θ),XB(t,θ^))≤2Ls/P<ε.2L d_{\infty}\left(X_B(t,\theta),X_B(t,\hat{\theta})\right)\leq2Ls/P<\varepsilon.

Adding these contributions proves the proposition. □\square

Parameters and proof of the configuration theorem

First fix L=2/ρL = 2/\rho and a rational ε>0\varepsilon> 0 such that

(6h2+2)ε<min⁡{δ,1}.(6h^2 + 2)\varepsilon< \min\{\delta,1\}.

The following order places the source alphabets after the list size and the number of layers.

  1. Take β,K\beta, K from Lemma 2.2 for L,εL, \varepsilon. Choose mm with L/m<β/2L/m < \beta/2, then rational 0<λ<10 < \lambda< 1 with λK<ε\lambda K < \varepsilon. Equation (3) now fixes pm>0p_m > 0.

  2. Choose s≥2s \ge2 with (1−pm)s<ε(1-p_m)^s < \varepsilon. Choose γ>0\gamma> 0 with s(2γ)2/β2<εs(2\gamma)^2/\beta^2 < \varepsilon. Take a positive multiple PP of the offset denominators large enough that

2LmP<γ,2LsP<ε.\frac{2L}{mP} < \gamma,\qquad\frac{2Ls}{P} < \varepsilon.

Set D=mPD = mP. This gives all of (17).

  1. Fix the integer dd in (9). Apply Lemma 6.1 with s,d,η=εs,d,\eta= \varepsilon to obtain r,μr,\mu. Choose rational 0<σ<10 < \sigma< 1 such that 4rd2σ<ε4r d^2 \sigma< \varepsilon. Only now take the alphabets of Theorem 2.1.

  2. Use any q≥hq \ge h with (h−1)/q<δ(h-1)/q < \delta for the fallback.

Every object used to construct the output is a fixed integer or a finite rational table, apart from the input Label Cover instance. In particular, the law μ\mu is independent of the terminal answer set and of the independent set later considered. The real functions, conditional expectations, and decoding maps occur only in the proof. For each fixed real δ>0\delta> 0 the strict inequalities above can be met with finite construction data.

Proof of Theorem 1.1. Apply Theorem 2.1 at the chosen σ\sigma, then use § 3. Proposition 3.1 gives a deterministic polynomial-time reduction in the binary input length. In the satisfiable case, Lemma 4.1 gives the phase map and excludes the fallback.

Suppose the input is unsatisfiable. The fallback has independence number h−1h-1, hence independence ratio less than δ\delta. On the sampling branch, fix a nonempty independent set AA. For every output vertex vv, with FF the function on its location’s grid, Lemma 5.1 gives

1A(v)≤h2F(xv)2.(23)1_A(v) \le h^2 F(x_v)^2. \tag*{(23)}

Indeed, a selected vertex has grid value at least 1/h1/h. At an unselected vertex the inequality holds also when a different copy at the same location was selected.

On an aligned pair, Proposition 7.4 bounds the expected right side of (23) by 6h2ε6h^2\varepsilon. On an unaligned pair bound the indicator itself by one. By (15) and the choice of σ\sigma, the probability of the latter event is less than 2ε2\varepsilon. The vertex law is uniform by Proposition 3.1. Thus

∣A∣∣V(H)∣=Pr⁡{v∈A}<6h2ε+2ε<δ.\frac{|A|}{|V(H)|} = \Pr\{v \in A\} < 6h^2\varepsilon+ 2\varepsilon< \delta.

The empty independent set satisfies the strict inequality as well. Taking the maximum over independent sets proves soundness.

Proofs of the coloring corollaries

Graphs

Proof of Corollary 1.2. In Theorem 1.1 take h=2h = 2, offsets 00, 1/21/2, and ρ=1/(8g)\rho= 1/(8g). On every satisfiable edge, subtracting the two phases introduces error at most 2ρ=1/(4g)2\rho= 1/(4g) relative to the half-turn. Lemma 4.2 gives a homomorphism to CgC_g. The unsatisfiable bound is the density assertion of the theorem.

Every odd cycle maps to K3K_3, hence to KcK_c for c≥3c \ge3. Take 0<δ<min⁡{1/3,1/c}0 < \delta< \min\{1/3, 1/c\}. A proper cc-coloring would have an independent class of density at least 1/c1/c. This proves the odd-cycle versus clique gap and hardness of finding such a coloring under the odd-cycle promise, by checking the output of a proposed polynomial-time algorithm.

For general A→BA \to B as in the corollary, some component of AA contains an odd cycle CgC_g. Choose 0<δ<min⁡{1/3,1/∣V(B)∣}0 < \delta< \min\{1/3, 1/|V(B)|\}. In the satisfiable case compose X→Cg→AX \to C_g \to A. A homomorphism X→BX \to B in the unsatisfiable case would have an independent fiber of density at least 1/∣V(B)∣1/|V(B)|, since BB is loopless. This is impossible.

For completeness, the other finite undirected templates give polynomial-time problems. A loop at the target permits constant acceptance. A loop in the source forces a target loop. For a bipartite source with an edge, K2→A→BK_2 \to A \to B. Testing bipartiteness separates the promises. For a nonempty edgeless source, accept the edgeless inputs. For the empty source, accept only the empty input. □

Remark 9.1 (Circular chromatic number). The circular clique Kp/qK_{p/q} joins residues modulo pp whose cyclic distance is at least qq, where p≥2qp \ge2q. For p=2k+1p = 2k + 1, q=kq = k its steps are precisely ±k\pm k, so it is isomorphic to C2k+1C_{2k+1}. Given ξ>0\xi> 0, take 1/k≤ξ1/k \le\xi. Corollary 1.2 then gives hardness of distinguishing χc(X)≤2+ξ\chi_c(X) \le2 + \xi from independence ratio below any fixed 0<δ<min⁡{1/3,1/(2+ξ)}0 < \delta< \min\{1/3, 1/(2 + \xi)\}. Indeed, qq consecutive residues are independent in Kp/qK_{p/q}, so a uniformly translated such interval pulls back under any circular coloring to an independent set of expected density q/pq/p. Taking the supremum over admissible circular colorings gives independence ratio at least 1/χc(X)1/\chi_c(X) for graphs with an edge. Edgeless graphs have independence ratio one.

Strong, rainbow, and linearly ordered colorings

Proof of Corollary 1.3. Use the regular configuration uj=j/hu_j = j/h and rational 0<ρ<1/(2h(h+1))0 < \rho< 1/(2h(h + 1)). Lemma 4.4 reads both colorings from the map supplied by Theorem 1.1. For k=h≥3k = h \ge3, take δ<1/c\delta< 1/c. The rainbow colors can be grouped into two nonempty parts to give a proper two-coloring, so the search problem on the simultaneous promise has a solution for every c≥2c \ge2. A proper cc-coloring on an unsatisfiable input would have an independent color class of density at least 1/c1/c. Testing a returned coloring on every edge therefore distinguishes the cases. Hardness on instances satisfying both promises gives hardness under each promise separately. For k=2k = 2, c≥3c \ge3, strong three-colorability is ordinary three-colorability. This is the case q=3q = 3 of Corollary 1.2. □

Proof of Corollary 1.5. Take h=3h = 3 in Corollary 1.3 and δ<1/d\delta< 1/d. In the satisfiable case, Lemma 4.6 gives an LO3\mathrm{LO}_3-coloring. An increasing inclusion into the cc-element palette preserves unique maxima. In the unsatisfiable case, each class of an LOd\mathrm{LO}_d-coloring would be independent, as a monochromatic triple has three maxima. Its largest class would have density at least 1/d1/d. □

Reconfiguration and monochromatic cliques

Proof of Corollary 1.4. For the first assertion choose the regular hh-gon and the radius of Lemma 4.5 for RR. Apply Theorem 1.1 with δ<1/d\delta< 1/d. Make the output a relational structure by including every ordering of every hyperedge as a tuple of its hh-ary relation. In the satisfiable case give vertex vv the color χ(φ(v))\chi(\varphi(v)). Lemma 4.5 puts the edge tuple in RR in its witnessing order. Symmetry gives membership in every order. In the unsatisfiable case any homomorphism to NAE⁡h(d)\operatorname{NAE}_{h}^{(d)} would give a proper dd-coloring, contrary to the density bound.

For the second assertion, use the finite relations in the monochromatic-clique equivalence of Banakh, Barsukov, and Nakajima, Lemma 6 [6]. Its source Rk:ℓ(c)R_{k:\ell}^{(c)} consists of the length-ℓ\ell words on cc colors in which each multiplicity is at most k−1k-1. Its target Rℓ:ℓ(d)R_{\ell:\ell}^{(d)} is NAE⁡ℓ(d)\operatorname{NAE}_{\ell}^{(d)}. The palette map from the containment hypothesis sends source words to target words. Indeed, a legal word colors an ℓ\ell-clique without a monochromatic kk-clique, so its recoloring cannot make the whole clique monochromatic. Containment implies k≤ℓk \le\ell, since otherwise a monochromatic ℓ\ell-clique would itself contradict containment.

Suppose first that ℓ<c(k−1)\ell< c(k-1). Then k≥2k \ge2 and ℓ≥2\ell\ge2. Give each color k−1k-1 distinguishable slots. The legal words are precisely the projections to colors of injections of the ℓ\ell positions into the c(k−1)c(k-1) slots. There is at least one injection and at least one spare slot. To reach a prescribed injection, fix the positions in turn. If another position occupies the desired slot, move that occupant to a vacant slot. Move the current position into its desired slot if necessary. Every previously fixed position occupies its own distinct target, so these moves preserve it. Projecting the sequence to colors and omitting repetitions gives a single-coordinate path of legal words. The relation is symmetric and reconfigurable. Thus the first assertion gives the hard finite PCSP used in the proof of Theorem 23 of Banakh et al. [6].

For these particular hard instances one can also see the transfer to graphs directly. This verifies the direction of the equivalence needed for hardness without a sparsification theorem. Use the circle coloring for Rk:ℓ(c)R_{k:\ell}^{(c)} just obtained from Lemma 4.5, with tolerance ρ∗\rho_*. Run the configuration reduction with regular ℓ\ell-gon offsets and a positive rational radius ρ\rho satisfying 2ρ<ρ∗2\rho< \rho_* and 6ρ<1/ℓ6\rho< 1/\ell. On the same vertices form the graph joining two vertices whenever they lie in a common hyperedge.

In the satisfiable case consider any kk-clique in this graph. Fix the phase tt of one vertex. Each other phase is within 2ρ2\rho of t+j/ℓt+j/\ell for some nonzero jj mod ℓ\ell, by applying the phase condition to a hyperedge shared with the fixed vertex. These assigned indices are distinct. Two vertices assigned the same index would be at distance at most 4ρ4\rho, whereas sharing any hyperedge gives distance at least 1/ℓ−2ρ>4ρ1/\ell-2\rho>4\rho. Include the fixed vertex at index zero and fill unused indices by their ideal phases. Lemma 4.5 sends the resulting ℓ\ell-tuple into Rk:ℓ(c)R_{k:\ell}^{(c)}. Thus the kk-clique cannot be monochromatic. The coloring used on the graph is the single map χ∘φ\chi\circ\varphi. In the unsatisfiable case, every hyperedge is an ℓ\ell-clique in the graph. A dd-coloring avoiding monochromatic ℓ\ell-cliques would therefore be a proper dd-coloring of the hypergraph. Choosing δ<1/d\delta< 1/d excludes it. The graph construction is deterministic and polynomial.

Finally suppose ℓ≥c(k−1)\ell\ge c(k-1). We spell out the affine integer argument of Banakh et al., Theorem 22 [6]. In their relational formulation an input may contain loops, and a looped vertex carries a monochromatic image of every clique; reject such inputs first. On a simple graph, enumerate all ℓ\ell-cliques, which takes polynomial time for fixed ℓ\ell. A source coloring gives a legal source word on each such clique. If ℓ>c(k−1)\ell> c(k-1), no such word exists. Accept exactly when there are no ℓ\ell-cliques. The same test works when the target relation is empty, since a graph avoiding all ℓ\ell-cliques has a target coloring and containment excludes any ℓ\ell-clique in a yes instance.

It remains to treat ℓ=c(k−1)\ell= c(k-1) with nonempty target relation. Then d≥2d \ge2 and 0<k−1<ℓ0 < k-1 < \ell, using k≤ℓk \le\ell. Every source word uses each color exactly k−1k-1 times. Introduce one integer variable per vertex and impose

∑v∈Qzv=k−1for every ℓ-clique Q.\sum_{v\in Q} z_v = k-1 \qquad\text{for every $\ell$-clique $Q$.}

A source coloring gives a solution by taking the indicator of one fixed color. In any integer solution, each clique has a positive entry since the sum is positive. It also has a nonpositive entry since the sum is strictly below ℓ\ell. The two sign classes give a target coloring. Thus testing integer feasibility separates the promises. This is a system of linear equations over the integers, whose feasibility is decidable in polynomial time by integer normal form. This proves the tractable side, including equality.

Use of AI

The proof presented in this paper was developed through an interactive dialogue with GPT-6.2 Astra (OpenAI) and Claude Opus 5.5 (Anthropic). The author used them to explore multiple possible proof strategies and directions, and the AI generated the initial draft under the author’s guidance. The author then critically examined the generated proof, verified each step for correctness and rigor, and revised it where necessary. The author takes full responsibility for the final content.

References

  1. [1]P. Austrin, A. Bhangale, and A. Potukuchi. Improved inapproximability of rainbow coloring. arXiv:1810.02784, 2018.arxiv.org/abs/1810.02784
  2. [2]S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM 45 (1998), 501–555.
  3. [3]T. Austin. On the failure of concentration for the ℓ∞-ball. Israel J. Math. 211 (2016), 221–238. arXiv version 4.DOI
  4. [4]S. Avvakumov, M. Filakovský, J. Opřšal, G. Tasınato, and U. Wagner. Hardness of 4-colouring G-colourable graphs. STOC 2025.arxiv.org/abs/2504.07592
  5. [5]L. Barto, J. Bulín, A. Krokhin, and J. Opřšal. Algebraic approach to promise constraint satisfaction. J. ACM 68 (2021), article 28.DOI
  6. [6]D. Banakh, A. Barsukov, and T.-V. Nakajima. Towards infinite PCSP: a dichotomy for monochromatic cliques. LICS 2026, LIPIcs 380, article 13. Full version.
  7. [7]J. Brakensiek and V. Guruswami. New hardness results for graph and hypergraph colorings. CCC 2016, LIPIcs 50, article 14.DOI
  8. [8]J. Brakensiek and V. Guruswami. Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. ECCC TR16-183, 2016, revised 2017 and 2021. Conference version, Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy, SODA 2018.arxiv.org/abs/1704.01937
  9. [9]J. Brakensiek and V. Guruswami. The quest for strong inapproximability results with perfect completeness. APPROX/RANDOM 2017, LIPIcs 81, article 4.
  10. [10]M. Braverman, S. Khot, N. Lifshitz, and D. Minzer. An invariance principle for the multi-slice, with applications. Full version, arXiv:2110.10725v2, 2025.
  11. [11]J. Bulín, A. Krokhin, and J. Opřšal. Algebraic approach to promise constraint satisfaction. STOC 2019.
  12. [12]Open Mathematics Courses. Large independent sets in three-colorable graphs: Label Cover and the graph of the reduction. Exercise 6.5, October 13, 2026.
  13. [13]I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra. Towards a proof of the 2-to-1 games conjecture? Theory of Computing 21 (2025), article 11.
  14. [14]I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring. SIAM J. Comput. 39 (2009), 843–873.
  15. [15]I. Dinur, O. Regev, and C. Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica 25 (2005), 519–535.
  16. [16]I. Dinur and D. Steurer. Analytical approach to parallel repetition. STOC 2014, 624–633.arxiv.org/abs/1305.1979
  17. [17]M. Filakovský, T.-V. Nakajima, J. Opřšal, G. Tasinato, and U. Wagner. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. STACS 2024, LIPIcs 289, article 34.
  18. [18]Y. Fei, D. Minzer, and S. Wang. On the hardness of 4-to-1 games with perfect completeness. ECCC TR26-179, September 14, 2026. arXiv:2610.12378v2.arxiv.org/abs/2610.12378
  19. [19]OpenAI. Perfect completeness for 2-to-1 games. OpenAI Math Release, item 105, September 23, 2026.DOI
  20. [20]M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. J. ACM 23 (1976), 43–49.DOI
  21. [21]V. Guruswami and S. Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discrete Math. 18 (2004), 30–40.DOI
  22. [22]V. Guruswami and E. Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. ECCC TR14-043, 2014.
  23. [23]V. Guruswami and S. Sandeep. d-to-1 hardness of coloring 3-colorable graphs with O(1) colors. ICALP 2020, article 62.DOI
  24. [24]V. Guruswami and S. Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms. SIAM J. Discrete Math. 34 (2020), 520–537.DOI
  25. [25]P. Hell and J. Nešetřil. On the complexity of H-coloring. J. Combin. Theory Ser. B 48 (1990), 92–110.DOI
  26. [26]OpenAI. Hardness of finding large independent sets in three-colorable graphs. OpenAI Math Release, item 106, September 24, 2026.DOI
  27. [27]S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. Combinatorica 20 (2000), 393–415.
  28. [28]A. Krokhin and J. Opřšal. The complexity of 3-colouring H-colourable graphs. FOCS 2019, 1227–1239.DOI
  29. [29]A. Krokhin, J. Opřšal, M. Wrochna, and S. Živný. Topology and adjunction in promise constraint satisfaction. SIAM J. Comput. 52 (2023), 38–79.DOI
  30. [30]A. Krokhin and D. Vagnozzi. Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard. ICALP 2026, LIPIcs 374, article 184.arxiv.org/abs/2508.14606
  31. [31]OpenAI. Hardness of coloring three-colorable graphs. OpenAI Math Release, Lean formalization scope.
  32. [32]E. J. McShane. Extension of range of functions. Bull. Amer. Math. Soc. 40 (1934), 837–842.DOI
  33. [33]T.-V. Nakajima, Z. Verwimp, M. Wrochna, and S. Živný. Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings. arXiv:2501.12062, 2025.arxiv.org/abs/2501.12062
  34. [34]T.-V. Nakajima and S. Živný. Linearly ordered colourings of hypergraphs. ACM Trans. Comput. Theory 14, nos. 3–4 (2023).DOI
  35. [35]F. P. Ramsey. On a problem of formal logic. Proc. London Math. Soc. (2) 30 (1930), 264–286.
  36. [36]R. Raz. A parallel repetition theorem. SIAM J. Comput. 27 (1998), 763–803.
  37. [37]M. Wrochna and S. Živný. Improved hardness for H-colourings of G-colourable graphs. SODA 2020, 1426–1435.DOI

Paper details

vlnc:W_xpc7c2rv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6.2 Astra, Claude Opus 5.5 (bare)

View statement
Looking for related papers…
Contents