Independent sets under a three-colorability promise

Source and verification

This article explains family 106 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Color classes and independent sets

For a nonempty finite simple graph $G$, write $n=|V(G)|$, $\alpha (G)$ for the largest independent-set size, and $\chi (G)$ for the least number of colors in a proper vertex coloring. Each color class is independent, so

$$\chi (G)\ge \frac{n}{\alpha (G)}.$$

In particular, a three-colorable graph has an independent set of size at least $n/3$. The existence of that set does not provide an efficient way to find it when the coloring is not supplied.

A promise problem asks an algorithm to distinguish two specified classes of inputs, with no requirement on inputs between them. Here the YES class has a coloring of the entire graph by three colors. The NO class has very small independence density $\alpha (G)/n$.

🏷️ The claimed all-vertex gap

Manuscript statement

For each fixed $0<\delta <1/3$, a deterministic polynomial-time reduction maps every explicitly encoded 3SAT formula to a nonempty finite simple unweighted graph satisfying

$$\begin{array}{rl}\text{YES}:& \chi (G)\le 3,\\ \text{NO}:& \alpha (G)<\delta n.\end{array}$$

The construction includes the explicit adjacency output. Its polynomial exponent and constants may depend on $\delta$. The YES coloring is not included in the output. (OpenAI, 2026)

All vertices must be colorable in the YES case. A statement allowing deletion of a small exceptional fraction would have a different promise.

Fix a palette size $c\ge 3$ and choose $\delta <1/c$. Every proper $c$-coloring would contain an independent class of size at least $n/c$, impossible in the NO case. Hence the claimed gap implies hardness of distinguishing three-colorable graphs from graphs not colorable with $c$ colors. More generally it supplies the same decision gap with a fixed $k$-colorable YES promise whenever $3\le k\le c$.

The independence-density conclusion is stronger than a large chromatic number alone. Adding many isolated vertices leaves chromatic number unchanged but makes the independence ratio approach one.

For search, suppose an algorithm always returned an independent set of size at least $\eta n$ on three-colorable inputs, for a fixed $\eta >0$. Choose $\delta <\min \{\eta ,1/3\}$. Run it on the reduced graph and check both independence and size. The check accepts every YES instance and no NO instance, regardless of the algorithm’s behavior outside its promise. Its running time must be polynomial on all inputs, or capped by its promised polynomial bound. Thus the decision reduction also explains the search obstruction.

🏷️ Label projections and circle-valued queries

The source begins with ordinary projection Label Cover: a bipartite system of local questions, answer alphabets, and edge maps sending a left answer to a right answer. It uses a perfectly satisfiable YES case and arbitrarily small fixed NO value. It does not assume a bound of two on projection fibers or consume the perfect two-to-one companion as a premise.

Consider tuples of questions. Moving through successive layers replaces one left question by a right question, inducing an answer projection $\pi :M\to M^{\prime }$. At each tuple, a phase vector assigns a point of the circle $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ to each possible product answer. The circle distance is

$$d_{\mathbb{T}}(s,t)=\underset{k\in \mathbb{Z}}{\min }|s-t-k|.$$

On a finite circle grid, give each phase space its sup distance over answer coordinates. Link $x\in {\mathbb{T}}^{M^{\prime }}$ to its pullback $x\circ \pi \in {\mathbb{T}}^M$ with length zero. Shortest paths through all these links define an extended pseudometric: distinct points can have distance zero, and points in different components can have infinite distance.

Let $T$ add $1/2$ to every phase. This is an involutive isometry on the chosen even grid. The output places an edge between distinct vertices at locations $x,y$ when

$$d(x,Ty)\le \frac{1}{8}.$$

The relation is symmetric because $T$ is an involutive isometry. Several output vertices may have the same location; their multiplicities realize an explicitly specified rational sampling law. There are no loops or parallel graph edges.

🏷️ The geometric completeness calculation

A satisfying Label Cover assignment gives a product answer at each tuple. Evaluating a phase vector at that answer defines $\phi$ from all phase spaces to the circle. Evaluation is nonexpanding within a phase space, and the satisfying projection constraints make it agree across every zero-length link. Therefore

$$d_{\mathbb{T}}(\phi (x),\phi (y))\le d(x,y).$$

Moreover $\phi (Ty)=\phi (y)+1/2$. For an output edge, set $a=\phi (x)$ and $b=\phi (y)$. Then

$$\begin{array}{rl}{d}_{\mathbb{T}}(a,b+1/2)& \le 1/8,\\ d_{\mathbb{T}}(a,b)& \ge 3/8>1/3.\end{array}$$

The second inequality uses the circle identity $d_{\mathbb{T}}(a,b)+d_{\mathbb{T}}(a,b+1/2)=1/2$. Divide the circle into the half-open intervals $[0,1/3)$, $[1/3,2/3)$, and $[2/3,1)$. Two phases in one interval have distance less than $1/3$, so adjacent vertices receive different interval colors. This proves the three-colorability mechanism for every multiplicity copy.

The three arcs represent the half-open color intervals; each boundary belongs to the interval starting there. The illustrative phases $a=1/24$ and $b=11/24$ have circle distance $5/12$, so they cannot share a color. The dashed chord marks the pair; its Euclidean length is not the circle distance. This picture illustrates the completeness calculation, not the soundness construction.

The construction first checks whether any phase location satisfies $d(x,Tx)\le 1/8$. If so, it outputs a fixed clique with independence density below $\delta$. This branch cannot occur for a satisfiable source, because evaluation would give $d(x,Tx)\ge 1/2$. This preliminary check handles possible degeneracy of the pseudometric rather than silently assuming it is a metric.

🏷️ Independent sets and bounded coordinate lists

For soundness, a large independent set produces bounded functions on the tuple phase spaces that change sign under $T$ and have a uniform Lipschitz bound. A dimension-independent approximation theorem approximates each such function by one depending on boundedly many answer coordinates. Such an approximant is called a junta; the coordinate bound depends on the requested accuracy, not the size of the answer alphabet.

The central obstacle is projection. A good approximation in product measure need not remain good after coordinates are identified. For example, on two independent uniform bits $x_1,x_2$, the event $x_1=x_2$ has probability $1/2$, while under the identification $x_1=x_2$ it has probability one. Product-measure estimates cannot simply be pulled back through a many-to-one coordinate map.

The source therefore selects lists for entire short subchains and inserts independent phase rotations at their layers. Lists are projected to the last layer so that their labels belong to one common answer set. An intersection between lists from separated subchains yields compatible answers for an intervening source constraint. Source soundness makes these intersections rare. The lists must be defined from the permitted local information before this argument can invoke the source game’s value.

🏷️ Alignment before sampling the lists

A distributional alignment lemma chooses a law on sets of layers before seeing the coordinate lists. On most selected layer sets, occurrences of each listed label can be assigned a common index. Its bound is independent of the label universe. The manuscript proves this using finite minimax, a Ramsey homogenization argument, and an order-invariant array construction; the current note uses that statement as the structural interface.

Next choose coefficients from $\{0,1/m,\dots ,1\}$ with probabilities proportional to ${\lambda }^k$ at level $k/m$, where $0<\lambda <1$. Phase locations are sums of the selected coefficients times independently sampled rotations, transported through the projections.

Enough layers make it likely that some coefficient equals one. That layer can absorb an auxiliary uniform phase shift without altering its law. Alignment limits dependence on zero-coefficient layers; comparison between neighboring positive levels bounds the probability of substantial dependence there. A dimension-independent influence estimate converts these controls into a small mean square for the odd functions, and hence a small independent-set density. The compatibility and coefficient estimates, rather than the elementary circle coloring, carry the difficult soundness argument.

Every grid size, layer count, alphabet, and rational coefficient law is fixed after choosing $\delta$. The finite probability experiment is expanded into integer vertex multiplicities, and all adjacency decisions use exact shortest-path distances. Thus probability describes the uniform distribution on an explicitly constructed deterministic graph. It does not introduce a chance of a faulty reduction.

🏷️ Key steps and proof outlines

Turning independence into a variance problem

In “The coefficient test and soundness,” the function extracted from an independent set is bounded by one and equals one on that set. Consequently its mean square under the vertex-sampling law bounds the independent-set density from above. The soundness proof aims to make this mean square small. (OpenAI, 2026)

After fixing an aligned chain and a selected set $B$ of layers, introduce independent uniform auxiliary phases $z_i\in \mathbb{T}$, one per selected layer. Let $H(z)$ be the resulting function, with coefficients and rotations temporarily fixed. Simultaneously adding $1/2$ to every $z_i$ changes its sign, so ${\mathbb{E}}_{z}H=0$. Define $E_{i}H$ by averaging only the coordinate $z_i$, and put

$$D_i=\Vert H-E_{i}H{\Vert }_2,X={\mathbb{E}}_z{H}^2.$$

The dimension-independent influence lemma supplies constants $\beta >0$ and $K$: if $X>ϵ$, then some $D_i\ge \beta$, whereas at most $K$ coordinates have $D_i\ge \beta /2$. These constants depend on the Lipschitz bound and tolerance, not on the answer alphabet. The two thresholds permit a robust comparison between neighboring coefficient levels.

Zero and positive coefficients have different proofs

Suppose $t_i=0$ and another coefficient equals one. Delete layer $i$ and approximate the remaining subchain function by its previously chosen junta. Alignment ensures that all coordinates used by this junta are assigned auxiliary phases indexed outside $i$. Thus the approximant is independent of $z_i$. The deletion error and junta approximation error are each less than $\gamma$, so contraction of the orthogonal projection $I-E_i$ gives

$$\mathbb{E}{D}_i^2<(2\gamma {)}^2.$$

Markov’s inequality and a union bound over the $s=|B|$ layers make the probability of a large zero-coefficient influence at most $s(2\gamma {)}^2/{\beta }^2$. The coefficient exactly equal to one is needed to absorb a uniform phase shift without altering its product law. Multiplication by a fractional coefficient would not commute with reduction modulo one in this way.

For positive coefficients, hold every other input fixed and write $d_k$ for $D_i$ when $t_i=k/m$. Lipschitz continuity gives

$$|d_k-d_{k-1}|\le L/m<\beta /2.$$

Hence $d_k\ge \beta$ forces $d_{k-1}\ge \beta /2$. The geometric probabilities satisfy $p_k=\lambda p_{k-1}$, so summing over levels transfers a high-threshold event to a lower-threshold event at a cost factor $\lambda$. Sum over coordinates and apply the deterministic bound of $K$ lower-threshold influences. The probability of any large positive-coefficient influence is at most $\lambda K$, independent of $s$.

This is the important economy: a direct union bound over all positive-coefficient layers would introduce $s$, while the influence-count bound introduces only the fixed $K$.

Returning to the actual finite graph

Choose parameters so that the probability of no full coefficient, the zero-coefficient error, and the positive-coefficient error are each below $ϵ$. Then $\mathrm{Pr}(X>ϵ)<3ϵ$. Since $0\le X\le 1$,

$$\mathbb{E}X\le ϵ+\mathrm{Pr}(X>ϵ)<4ϵ.$$

On the event of a full coefficient, absorb the auxiliary phases into that layer’s independent rotations. This identifies the auxiliary experiment’s mean square with the continuous location experiment used to construct vertices. Rounding each rotation to a grid of mesh $1/P$ changes a location by at most $s/P$ in sup distance. The squared function changes by at most $2Ls/P$, because $|u^2-v^2|\le 2|u-v|$ for $u,v\in [-1,1]$. Paying another $ϵ$ for this error and another for missing a full coefficient yields the source’s $6ϵ$ density bound on aligned chains. The alignment theorem and outer-game soundness pay for the remaining exceptional chains.

See Also

• Perfect two-to-one games separates ordinary projection hardness from the additional exact-fiber requirement; it is not needed as an input to this family.
• Approximation thresholds explains the general gap-to-hardness deduction and other uses of local coordinate lists.
• Forbidden-subgraph coloring studies existence bounds under graph restrictions, whereas the present question is computational recovery under a coloring promise.

🏷️ Manuscripts and verification scope

• Hardness of finding large independent sets in three-colorable graphs — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The stated scope includes nonempty finite simple output graphs, three-colorable YES instances, strictly bounded independence density on NO instances, and the complete adjacency-matrix output in the running-time bound. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Hardness of finding large independent sets in three-colorable graphs.