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 -gon gives a strong -coloring and a rainbow -coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of for every nonempty symmetric reconfigurable relation with , and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich -to- Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes . 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 , the decision problem accepts inputs with a homomorphism and rejects inputs with . A homomorphism preserves every relation. For graphs it sends each edge to an edge. Taking and to be cliques gives approximate graph coloring.
For a hypergraph , let 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 is a set of distinct vertices.
Write and give it the distance , 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 , distinct rational offsets in , a rational such that
and a real . There is a deterministic polynomial-time reduction from 3SAT to nonempty -uniform hypergraphs with these properties.
(i) If the input is satisfiable, there is a map . Every edge has an ordering and a for which
(ii) If the input is unsatisfiable, then .
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 and every , there is a deterministic polynomial-time reduction from 3SAT to nonempty graphs such that satisfiable instances map to and unsatisfiable instances have independence ratio less than . Consequently PCSP(, ) is NP-hard for every . More generally, PCSP(, ) is NP-hard for every pair of finite loopless undirected graphs with 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 keeps the two promises disjoint for every . Indeed, write . A uniform rotation of a fixed independent -set of contains each vertex with probability . Its preimage under has expected size .
Corollary 1.3 (Strong and rainbow colorings). For every and , a deterministic polynomial-time reduction from 3SAT produces an -uniform hypergraph with a strong -coloring and a rainbow -coloring in the satisfiable case, and independence ratio below in the unsatisfiable case.
For all fixed , except , it is NP-hard to find a proper -coloring of a -uniform hypergraph promised to be strongly -colorable. For this also holds under the rainbow -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 , let be the relation of nonconstant -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 for the family consisting of a monochromatic -clique in each of colors. An arrow 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 be a nonempty symmetric reconfigurable relation on a finite set, where . For every with , the problem PCSP() is NP-hard.
Let , , , be positive integers with . If , then is solvable in polynomial time via affine integer programming. If , then it is NP-hard.
A linearly ordered coloring gives each edge a unique vertex of maximum color. Let denote the relation of triples with a unique maximum on an ordered -element palette.
Corollary 1.5 (Linearly ordered triples). For every fixed , the problem on -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 lifts a phase vector to . 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 to every coordinate adds to the evaluation. We can therefore test a configuration by looking for one grid point 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 be a truncated distance function equal to one at its locations. At a selected location , at least one of the translates of must have bump value zero. Otherwise the nearby selected vertices would form an edge. Thus the difference between and the average of its translated values is at least . 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 . 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 has coefficient zero, we use the list for the other layers. A final answer in that list must be assigned somewhere other than . 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 -colorable inputs, , Brakensiek and Guruswami reached colors [7]. Bulín, Krokhin, and Opršal reached , including five colors at [11, 5]. Krokhin and Opršal proved hardness against for every non-bipartite three-colorable source [28]. Wrochna and Živný reached colors for . 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 [29 Theorem 1.8]. Avvakumov, Filakovský, Opršal, Tasinato, and Wagner proved hardness against 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 -to-1 hardness, Guruswami and Sandeep obtained the density gap with -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 against .
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 strong colors for every , and with strong colors for [7 Theorem 1.3]. Under their induced V Label Cover conjecture, they obtained separate density gaps for strong colors when , and rainbow colors when [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 rainbow colors in the range where this is a rainbow promise, and settled the boundary for [1]. Guruswami and Sandeep extended boundary two-color hardness to [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 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 -tuples on colors and the surjective -tuples on 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 . 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 for the fixed target palette [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 as Theorem 9, citing the Krokhin–Vagnozzi preprint for the starting case. Their Corollary 10 gives all conditionally [6]. For uniformity at least four, Nakajima, Verwimp, Wrochna, and Živný proved hardness for all [33].
Label Cover and coordinate approximation
Write . 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 norms below use these laws.
The source problem
A Label Cover instance has finite question sets , nonempty answer sets , and a nonempty explicit list of test occurrences. Each occurrence specifies a left question , a right question , and a total map . Its value is
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 , 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 .
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 . 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 with and every , there is an integer with the following property. For any and any -Lipschitz , there is a coordinate set , , such that
Indeed, apply Austin’s Theorem 1.1 to the uniform interval with modulus . Take the error below . The pointwise difference has absolute value at most two, giving the stated 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 , let average coordinate while retaining all others. Set
Both and are orthogonal projections. In particular, changing a function by in changes by at most .
Lemma 2.2 (Influence detection and count). For every , , and , there are and independent of such that every -Lipschitz satisfies
Proof. Set . Choose a set of at most coordinates so that satisfies . If has mean zero and , then has mean zero and .
To bound this last norm, expand using the commuting projections . For , put
Their sum is , since . Two distinct summands are orthogonal by averaging at a coordinate in their symmetric difference. Conditioning on retains exactly the summands with . The constant summand vanishes. Consequently
Take .
For the count, approximate to error less than by a junta on at most coordinates. Outside its coordinate set , so . This part holds for every mean.
The reduction
Fix the configuration and density in Theorem 1.1. The construction uses integers , , and . Take divisible by the denominators of all the offsets. Other finite data are a rational number and a rational probability law on . The choices in § 8 fix all these data before the input formula is read. Put
We describe the reduction on the output of Theorem 2.1.
A space of phase assignments
At layer , form all question tuples and the corresponding answer set
Both products have positions. Occurrences of the same question at different positions remain separate positions. At adjacent layers , , take all pairs of question tuples that agree off position . For each occurrence between their questions at position , impose the map applying its projection at that position and the identity elsewhere.
Place a separate copy of at each question tuple of layer . A grid point is an assignment of a phase to every answer of that tuple. Let be the disjoint union of the grids. Define an undirected weighted link graph on . Within a grid, link each pair with length its sup circle distance. For an imposed map , link each point of its target grid to of its source grid with length zero. The direction of this pullback is opposite to the answer map.
Let 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 , let in each grid. Within-grid lengths are translation invariant. On a projection link,
Thus and its inverse take links to links of the same length. Each is an isometry of . We use the same notation for arbitrary diagonal translations on a continuous product torus.
Configuration tests
Choose an integer with . Denote by the hypergraph of all -subsets of . First test whether there exist and with
If so, output and stop. We call this the fallback. On the other branch, the closed balls of radius about the translates of any one center are pairwise disjoint.
The vertices on this branch will have locations . Declare a set of distinct vertices to be an edge if it has an ordering and a witness such that
Both tests range over the entire grid union. In particular, 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 independent uniform occurrences from . Write their questions as . They determine the occurrence chain
For , let be the composite of the imposed maps along this chain. It acts at positions through . We use and .
Independently sample . In each layer , draw a coefficient independently from the law
Draw independent rotations uniformly from , for . These are real representatives in . 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 , , define the phase vector
The location of the sampled outcome is in the grid at . Each summand has denominator dividing , 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 -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 . Each of the 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 independent of the instance. Indeed, , the coefficient table, and the possible numbers of rotation entries are fixed. For each conditional outcome of probability emit distinct vertices with its location. The count is per chain and 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 . The weights are nonnegative integers at most . 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 and is a finite scaled distance, the tests are and , respectively. An infinite distance fails either comparison.
For the second test enumerate centers and ordered -tuples of distinct vertex indices. Store each successful edge once under its sorted indices. This costs comparisons after the distances are available. All loops here have polynomial total cost for fixed and alphabets.
There is even an edge in the sampling branch. Fix a chain and a 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 , for each , since their denominators divide . These positive-probability outcomes have distinct constant locations and witness an edge about the zero vector of that grid. The fallback also contains an edge.
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 , let be the product of its assigned answers. Define on its grid. Evaluation is nonexpanding on within-grid links. If is an imposed map from to , satisfaction gives . 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
At any , the distance between translates is at least . This excludes (1). Give vertex the phase . For an edge with witness , nonexpansion in (2) gives the required inequalities with . □
An antipodal pair
Use on with edges of difference . For two offsets , the two errors relative to a common translate give an error at most in the displacement.
Lemma 4.2 (Odd-cycle rounding). Let . Suppose a graph has a phase map under which the displacement on every edge has circle distance at most from . Then the graph maps to .
Proof. At a vertex with real phase lift , give the color
Here . Changing the lift adds a multiple of to the bin index. On an edge, choose the other lift so that
Writing for the fractional part gives
The interval includes its endpoints, and the floor assigns a boundary point to the bin starting there. Since , the colors differ by or . □
Remark 4.3. For , Open Mathematics Courses, Exercise 6.5, observes that the three-bin completeness argument works for any antipodal displacement cutoff strictly below [12]. For the configuration theorem the displacement cutoff is twice the per-vertex radius. We use .
A regular polygon
Lemma 4.4 (Two partitions of the circle). Use the offsets , , with and . On every hypergraph satisfying the phase condition of Theorem 1.1, the partitions into and 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 . The corresponding actual phases have distance at least . A bin of width cannot contain two such points.
Choose a lift of the translation on an edge and write its lifts as , with . Set for the next copy of the first vertex. Every successive gap lies in
The positive lower bound gives cyclic order, including the gap across the seam. If a lifted bin were empty, the last lift before would be strictly less than and the next would be at least . 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 contains and a single-coordinate path in from to . There are a rational and a map such that
Every nonempty symmetric reconfigurable relation has this property.
Proof. Write the path as . Schedule its steps at distinct increasing interior times of . Let be the current tuple, using the new value at a step. It equals near zero and near . Extend it to the real line by
At the seam , the new value of entry is , its value on the left. Rotation gives the same equality at every seam. After intervals each entry returns to its original position. The extension is periodic with period one. Set . Then .
If there are steps, their times repeat with period . Choose smaller than 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 . A closed interval meets at most one step. If it meets one, the tuples on its two sides belong to by symmetry and differ in one coordinate. Sampling entry at an arbitrary therefore produces one of these two tuples. This includes sampling exactly at the step. If the interval meets none, it gives . Equation (5) identifies the sampled entries with . Finally, symmetry puts the rotation of any in , and reconfigurability supplies the path.
Lemma 4.6 (Merging colors on triples). A strong four-coloring of a 3-uniform hypergraph gives an -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 in the sampling branch. The choice of precedes every random choice in the analysis. Its set of locations is . The vertex set retains multiplicities throughout. Only forgets them.
A function with zero integral on each diagonal circle
Lemma 5.1 (Translated bump). Put . There is a function constant on zero links such that for every . On the grid at each tuple it has an -Lipschitz extension satisfying
Along any chain, write . For ,
Proof. On the whole grid union define
Take at infinite distance. Suppose and every summand is positive. For each , choose with . Failure of (1) makes the closed radius- balls at this center disjoint. Thus the are distinct. Choose one selected vertex at each. These vertices form an edge by (2) with . This contradicts independence. At least one summand is zero. Since and the other summands are at most one, .
On a component meeting , distance to is 1-Lipschitz for the path pseudometric. On a component disjoint from , is constant. A within-grid link bounds path distance from above by sup circle distance. It follows that restricted to a grid is -Lipschitz. Points at zero distance have equal values under , as do their simultaneous translates. Hence agrees across zero links.
At the tuple , extend the bump by the McShane formula and clip to the interval [32]. Explicitly, with denoting this tuple’s grid, let
Every term is nonnegative. The inner minimum is -Lipschitz. At a grid point , every term is at least and the term gives equality. The outer minimum preserves this value and the Lipschitz bound. Now put
Every required shift preserves the grid, so extends . Its two terms take values in and each has Lipschitz constant at most . On the diagonal circle , the integral of each translated bump equals the integral of the first bump by . This gives (6) at every .
Finally, round to a grid point at sup distance at most . Pullback preserves this upper bound. The grid points and are joined by a sequence of zero links, so agrees at the two endpoints. The two rounding errors give (7), independently of the length of the composite.
Lists on a subchain
The only subchains that will need lists have layers. They are the possible results of deleting one layer from a sampled -set. Fix . For and a fixed coefficient vector , consider
The rotation entries now have continuous product law. In one coordinate of , each block contributes one scalar multiplied by a number in . Hence changing the whole rotation array by sup distance changes the phase vector by at most in circle sup distance. This holds for all projection maps, including those with large fibers. The function is therefore -Lipschitz.
Lemma 5.2 (Local choice of lists). For each fixed chain and each , there are sets , , with
For every there is a junta on entries with such that . The lists depend only on the tuples in , 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 whose coordinate conditional expectation has error less than , choose the first in a fixed ordering. Use that conditional expectation as . Union the chosen indices within each block over the vectors . 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:
Each has size at most . The projection in this formula can use occurrences outside . We decode from the selected coordinates before this terminal projection.
Lemma 5.3 (Decoding separated lists). If and satisfy , then
Proof. Put , and condition on all occurrences except . Each tuple in has left question at position . Its remaining entries are fixed. All projections internal to that subchain use occurrences with indices below . The left list rule consequently depends on only through . On , position already has right question and all internal projections avoid . Its list rule depends on only through . The family of functions 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 of all its selected answers. This gives at most left candidates as a function of the left question and at most right candidates as a function of the right question. Order and pad the lists to length 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 , the left answer was acted on by exactly , and the right answer was unchanged. Thus one of the labelings satisfies . Conditional on the background this occurrence still has its original uniform law. Each labeling satisfies it with probability at most . A union bound and then averaging over the background prove the claim.
Soundness II. Finite distributional alignment
For we seek a map such that
In fact, (11) is equivalent to the absence of a label common to all 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 . For example, with 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 , and every , there exist and a rational probability law on with the following property. Let be any set. For every give a list of size at most . Assume
With probability at least over , a map satisfying (11) exists.
Proof. We may assume 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 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 , define an index
Every occurrence satisfies
The lower bound follows from the definition. If the upper bound failed, a list attaining the maximum would be strictly to the right of and would share with it. This proves the upper bound. We will round this one index in the same way for every occurrence of .
A good set for any distribution of patterns. Choose an integer with . By the finite Ramsey theorem take large enough that every coloring of the -subsets of in at most colors has a homogeneous set of size [35]. This choice precedes the distribution of patterns.
Now give the allowed patterns any probability distribution . For an -set , form numbers, one for each and . With , the number is
Here is computed on the whole pattern on . Color by the vector of the integer parts of times these numbers. There are at most colors.
In a homogeneous set of size , write the points in order as
Use as boundaries. Round to when , with , . For each pattern, assign every appearing label by this rounding and send absent labels anywhere in . Consider . If or , (12) prevents any label of from rounding to . For , the two points occupy the same rank when inserted separately into . The -sets and have the same Ramsey color. For any fixed slot of , 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 . Homogeneity bounds this difference by . A union bound over deletions and at most slots gives
The set here may depend on .
One rational law for all patterns. Let 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 by (14). Double the weight of every pattern for which that set admits no assignment. The total weight increases by a factor at most . If a particular pattern fails in of rounds, its own weight is . It follows that
The second term is less than . Choose to make the first term less than . Give each of the chosen sets mass , adding masses for repetitions. This rational law has failure probability less than for every pattern. Every actual list family induces such a pattern, and assignments transfer back to its labels.
Call a chain and aligned when (11) holds for their terminal lists. Apply Lemma 6.1 with . For a chain whose separated lists are all disjoint, the conditional failure probability over is at most . There are at most ordered pairs of subsets of . Lemma 5.3 and the union bound give
The order of the choices matters here. The single law 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 , and choose an assignment as in (11). Put . Write for independent uniform real rotation entries in . Let consist of independent Haar phases, independent of all rotations and coefficients. Define
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 , the function is -Lipschitz, has absolute value at most one, and satisfies .
Proof. Each coordinate of reads one with coefficient one. Thus is nonexpanding in and . With fixed, Haar invariance and (6) give
The range and Lipschitz bounds follow from those of . The identity also covers the all-zero coefficient vector.
Take from Lemma 2.2 at . In this section assume
For fixed , let
Applying Lemma 2.2 pointwise in gives
The count holds for all coefficient vectors. Its bound was fixed independently of .
Deleting a zero coefficient
Call a coefficient full when it equals one and let be the event that at least one coefficient is full. By independence, .
Lemma 7.2. Fix and with . Then
Proof. Choose with . Then . Put and . In the rotation array on , modify only block by setting
Here braces mean the representative in of a sum modulo one. Conditional on , 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 . Composition of the projections gives for every
Indeed, the deleted term has coefficient zero. In the translated block, the added phase is . The integer removed by taking the representative in (20) disappears in the phase sum because . Consequently (7) gives the pointwise bound
This also treats deletion of the minimum of .
Take the junta from Lemma 5.2. Preservation of the rotation law at every fixed gives
Only entries in block can introduce dependence on into this junta. Each such selected entry has , hence by alignment. Therefore is independent of . Apply , acting on in the joint product space. It kills this junta and has norm at most one. We obtain
For each fixed , Markov’s inequality and a union bound over its zero coefficients now apply. After averaging in ,
Lowering a positive coefficient
Lemma 7.3. Under the product laws on ,
Proof. Fix , the array , and the other coefficients. At level , denote by and its -influence by . Moving down one level changes each phase coordinate by distance at most , since each rotation is in . Hence
If , the preceding level has . Its probability is . It follows that
Average over the fixed data, use the union bound over , and apply (19). The right side becomes at most . 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 ,
Proof. By (18), if , 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 , , and , respectively, by (21) and Lemma 7.3. All three are less than . Since ,
To remove , fix and choose any one full block . Translate its rotations by (20), now retaining all blocks. The same coordinate computation gives . The conditional rotation law is unchanged for each , so
Multiply by the probability of each such and sum. The resulting contribution to the unshifted square is below by (22). On the square is at most one, which adds less than .
Finally couple the discrete rotations by . They have exactly the independent uniform law of the construction. Each phase coordinate in (4) moves by at most . Since , the difference of the two squared function values is at most
Adding these contributions proves the proposition.
Parameters and proof of the configuration theorem
First fix and a rational such that
The following order places the source alphabets after the list size and the number of layers.
Take from Lemma 2.2 for . Choose with , then rational with . Equation (3) now fixes .
Choose with . Choose with . Take a positive multiple of the offset denominators large enough that
Set . This gives all of (17).
Fix the integer in (9). Apply Lemma 6.1 with to obtain . Choose rational such that . Only now take the alphabets of Theorem 2.1.
Use any with 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 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 the strict inequalities above can be met with finite construction data.
Proof of Theorem 1.1. Apply Theorem 2.1 at the chosen , 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 , hence independence ratio less than . On the sampling branch, fix a nonempty independent set . For every output vertex , with the function on its location’s grid, Lemma 5.1 gives
Indeed, a selected vertex has grid value at least . 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 . On an unaligned pair bound the indicator itself by one. By (15) and the choice of , the probability of the latter event is less than . The vertex law is uniform by Proposition 3.1. Thus
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 , offsets , , and . On every satisfiable edge, subtracting the two phases introduces error at most relative to the half-turn. Lemma 4.2 gives a homomorphism to . The unsatisfiable bound is the density assertion of the theorem.
Every odd cycle maps to , hence to for . Take . A proper -coloring would have an independent class of density at least . 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 as in the corollary, some component of contains an odd cycle . Choose . In the satisfiable case compose . A homomorphism in the unsatisfiable case would have an independent fiber of density at least , since 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, . 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 joins residues modulo whose cyclic distance is at least , where . For , its steps are precisely , so it is isomorphic to . Given , take . Corollary 1.2 then gives hardness of distinguishing from independence ratio below any fixed . Indeed, consecutive residues are independent in , so a uniformly translated such interval pulls back under any circular coloring to an independent set of expected density . Taking the supremum over admissible circular colorings gives independence ratio at least 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 and rational . Lemma 4.4 reads both colorings from the map supplied by Theorem 1.1. For , take . 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 . A proper -coloring on an unsatisfiable input would have an independent color class of density at least . Testing a returned coloring on every edge therefore distinguishes the cases. Hardness on instances satisfying both promises gives hardness under each promise separately. For , , strong three-colorability is ordinary three-colorability. This is the case of Corollary 1.2. □
Proof of Corollary 1.5. Take in Corollary 1.3 and . In the satisfiable case, Lemma 4.6 gives an -coloring. An increasing inclusion into the -element palette preserves unique maxima. In the unsatisfiable case, each class of an -coloring would be independent, as a monochromatic triple has three maxima. Its largest class would have density at least . □
Reconfiguration and monochromatic cliques
Proof of Corollary 1.4. For the first assertion choose the regular -gon and the radius of Lemma 4.5 for . Apply Theorem 1.1 with . Make the output a relational structure by including every ordering of every hyperedge as a tuple of its -ary relation. In the satisfiable case give vertex the color . Lemma 4.5 puts the edge tuple in in its witnessing order. Symmetry gives membership in every order. In the unsatisfiable case any homomorphism to would give a proper -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 consists of the length- words on colors in which each multiplicity is at most . Its target is . The palette map from the containment hypothesis sends source words to target words. Indeed, a legal word colors an -clique without a monochromatic -clique, so its recoloring cannot make the whole clique monochromatic. Containment implies , since otherwise a monochromatic -clique would itself contradict containment.
Suppose first that . Then and . Give each color distinguishable slots. The legal words are precisely the projections to colors of injections of the positions into the 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 just obtained from Lemma 4.5, with tolerance . Run the configuration reduction with regular -gon offsets and a positive rational radius satisfying and . On the same vertices form the graph joining two vertices whenever they lie in a common hyperedge.
In the satisfiable case consider any -clique in this graph. Fix the phase of one vertex. Each other phase is within of for some nonzero mod , 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 , whereas sharing any hyperedge gives distance at least . Include the fixed vertex at index zero and fill unused indices by their ideal phases. Lemma 4.5 sends the resulting -tuple into . Thus the -clique cannot be monochromatic. The coloring used on the graph is the single map . In the unsatisfiable case, every hyperedge is an -clique in the graph. A -coloring avoiding monochromatic -cliques would therefore be a proper -coloring of the hypergraph. Choosing excludes it. The graph construction is deterministic and polynomial.
Finally suppose . 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 -cliques, which takes polynomial time for fixed . A source coloring gives a legal source word on each such clique. If , no such word exists. Accept exactly when there are no -cliques. The same test works when the target relation is empty, since a graph avoiding all -cliques has a target coloring and containment excludes any -clique in a yes instance.
It remains to treat with nonempty target relation. Then and , using . Every source word uses each color exactly times. Introduce one integer variable per vertex and impose
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 . 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]P. Austrin, A. Bhangale, and A. Potukuchi. Improved inapproximability of rainbow coloring. arXiv:1810.02784, 2018.arxiv.org/abs/1810.02784
- [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]T. Austin. On the failure of concentration for the ℓ∞-ball. Israel J. Math. 211 (2016), 221–238. arXiv version 4.DOI
- [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]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]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]J. Brakensiek and V. Guruswami. New hardness results for graph and hypergraph colorings. CCC 2016, LIPIcs 50, article 14.DOI
- [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]J. Brakensiek and V. Guruswami. The quest for strong inapproximability results with perfect completeness. APPROX/RANDOM 2017, LIPIcs 81, article 4.
- [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]J. Bulín, A. Krokhin, and J. Opřšal. Algebraic approach to promise constraint satisfaction. STOC 2019.
- [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]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]I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring. SIAM J. Comput. 39 (2009), 843–873.
- [15]I. Dinur, O. Regev, and C. Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica 25 (2005), 519–535.
- [16]I. Dinur and D. Steurer. Analytical approach to parallel repetition. STOC 2014, 624–633.arxiv.org/abs/1305.1979
- [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]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]OpenAI. Perfect completeness for 2-to-1 games. OpenAI Math Release, item 105, September 23, 2026.DOI
- [20]M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. J. ACM 23 (1976), 43–49.DOI
- [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]V. Guruswami and E. Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. ECCC TR14-043, 2014.
- [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]V. Guruswami and S. Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms. SIAM J. Discrete Math. 34 (2020), 520–537.DOI
- [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]OpenAI. Hardness of finding large independent sets in three-colorable graphs. OpenAI Math Release, item 106, September 24, 2026.DOI
- [27]S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. Combinatorica 20 (2000), 393–415.
- [28]A. Krokhin and J. Opřšal. The complexity of 3-colouring H-colourable graphs. FOCS 2019, 1227–1239.DOI
- [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]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]OpenAI. Hardness of coloring three-colorable graphs. OpenAI Math Release, Lean formalization scope.
- [32]E. J. McShane. Extension of range of functions. Bull. Amer. Math. Soc. 40 (1934), 837–842.DOI
- [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]T.-V. Nakajima and S. Živný. Linearly ordered colourings of hypergraphs. ACM Trans. Comput. Theory 14, nos. 3–4 (2023).DOI
- [35]F. P. Ramsey. On a problem of formal logic. Proc. London Math. Soc. (2) 30 (1930), 264–286.
- [36]R. Raz. A parallel repetition theorem. SIAM J. Comput. 27 (1998), 763–803.
- [37]M. Wrochna and S. Živný. Improved hardness for H-colourings of G-colourable graphs. SODA 2020, 1426–1435.DOI