Episode 106, October 2026

Three colors, no help?

A claimed proof that a three-coloring promise does not make large independent sets easy to find

Covers result 106 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 106: Three colors, no help? A circle of phases cut into three colored arcs, with one point and its neighbors near the opposite side.

5:59. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

A proper coloring gives adjacent vertices different colors. If a graph can be colored with three colors, one color class holds at least a third of the vertices, and no two of them are adjacent: it is an independent set. Deciding whether a graph is three-colorable is NP-complete. But suppose it is promised to be: can we color it with four colors, or ten, or find an independent set of 1% of the vertices?

Algorithms do poorly: Bansal, Huang and Lee’s method uses O(n^0.19539) colors, improving Kawarabayashi, Thorup and Yoneda, and newer randomized preprints report somewhat smaller exponents. On the hardness side, Khanna, Linial and Safra showed that four colors are NP-hard, Barto, Bulín, Krokhin and Opršal five, and Fei, Minzer and Wang’s recent theorem on 4-to-1 games, through reductions of Guruswami and Sandeep and of Krokhin, Opršal, Wrochna and Živný, gives any fixed number. Independent sets are a stronger question: small independent sets force many colors, but adding isolated vertices keeps the colors while making the independent sets huge. Earlier results reached it from conjectures (Dinur, Mossel and Regev; Braverman, Khot, Lifshitz and Minzer), for almost three-colorable graphs with density 1/9 (Dinur, Khot, Perkins and Safra), or with an eight-coloring promise (Fei, Minzer and Wang).

Result 106 is one OpenAI preprint (21 pages) dated September 24, 2026. For every fixed δ below 1/3 it gives a deterministic polynomial-time reduction from 3-SAT to graphs: satisfiable formulas give three-colorable graphs, and unsatisfiable ones give graphs in which every independent set has fewer than δ times the number of vertices. Since a graph colored with c colors has an independent set of at least a c-th of its vertices, coloring three-colorable graphs with any fixed number of colors is NP-hard.

What is new

The coloring consequence was already known through Fei, Minzer and Wang, and also follows from result 105. The new part is the independent-set bound under the full three-coloring promise, proved from ordinary label cover with no condition on the sizes of its projection fibers.

Where it stands

Posted as a preprint: OpenAI, 21 pages, dated September 24, 2026, released October 6
Peer reviewed: Not yet
Checked in Lean: OpenAI published a Lean proof of the main theorem; we have not run the check

Last checked October 19, 2026. The preprint has not been revised since its release; its text cites preprints posted after its September 24 date line. OpenAI published a Lean formalization, 454 files and 94,095 lines importing only Mathlib, matched against its comparator statement: a polynomial-time Turing-machine reduction, with a polynomial bound on the output graph, from three-colorable graphs to graphs with independence number below δn. We found no unproved steps; it proves its own inputs, a PCP theorem, parallel repetition and a Friedgut-type junta theorem in place of Austin’s. We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Phases on a circle. Start from label cover with perfect completeness and tiny value on unsatisfiable formulas. Build chains of question tuples, replacing one question at a time. A vertex is a point, drawn by a finite random experiment, that assigns a phase on the circle to every possible answer of a tuple; projections link points at distance zero, and an edge joins x and y when x is within 1/8 of y shifted by half a turn.
Completeness. If the formula is satisfiable, evaluating every point at the satisfying answer gives each vertex one phase, and adjacent vertices get phases at least 3/8 apart, so the three arcs [0, 1/3), [1/3, 2/3), [2/3, 1) color the graph properly.
Few coordinates matter. An independent set gives bounded functions on the phase spaces that flip sign under the half turn and share a Lipschitz bound. Austin’s junta theorem, a continuous counterpart of Friedgut’s, approximates them using a bounded number of answer coordinates, however many there are. Coordinate lists are chosen for whole stretches of a chain, with random rotations at every layer; two separated stretches sharing an answer would satisfy a label cover test in between, which low label cover value makes rare.
A density bound. An alignment lemma (finite minimax, Ramsey-type homogenization, random arrays) assigns each listed label, on most sampled sets of layers, one index shared by all its occurrences. Coefficients sampled at finitely many levels with geometrically decreasing probabilities, and a bound on influential coordinates, give a small mean square and hence a small independent set. The random experiment is expanded exactly into unweighted vertices, so the reduction is deterministic.

The numbers in the video

A random 15-vertex graph with a planted three-coloring (42 edges): chromatic number 3, color classes of 5, largest independent set 6.
K₄ plus isolated vertices keeps 4 colors while its independence ratio rises: 0.700, 0.970, 0.997.
The completeness rule on 20,000 random pairs of phases: 5,071 edges, every one joining phases at least 3/8 apart, all properly colored by the three arcs.
n^0.19539, ignoring the constant: about 15 for a million vertices, 57 for a billion.

Read the source

Hardness of finding large independent sets in three-colorable graphs (PDF), 21 pages.
The Lean scope note.
The collection’s catalog, where this is result 106.

The paper

OpenAI groups related papers into one result; this one has a single paper.

Hardness of finding large independent sets in three-colorable graphs

Transcript

Read the full script

0:00Coloring with a promise

A proper coloring gives adjacent vertices different colors. If a graph can be colored with three colors, one of the three color classes holds at least a third of the vertices, and no two of them are adjacent: it is an independent set. Deciding whether a graph is three-colorable is NP-complete. But suppose we are promised that it is. Can we then color it with four colors, or ten, or at least find an independent set of 1% of the vertices? In our example, 15 vertices with a hidden three-coloring, the largest independent set has 6 vertices. Algorithms do poorly. The best known polynomial-time method, by Bansal, Huang and Lee, improving Kawarabayashi, Thorup and Yoneda, uses about n^0.195 colors, up to a constant factor; for a million vertices that power is about 15, and newer randomized preprints report somewhat smaller exponents. Hardness lagged far behind. Khanna, Linial and Safra showed that four colors are NP-hard, and Barto, Bulín, Krokhin and Opršal five. Recently Fei, Minzer and Wang proved a games theorem that, through earlier reductions, makes any fixed number of colors NP-hard. A stronger question is about independent sets. Is it NP-hard to tell three-colorable graphs from graphs whose independent sets are all tiny? Small independent sets force many colors, but not the other way round: adding isolated vertices to a graph keeps its colors but makes its independent sets huge. Dinur, Mossel and Regev, and later Braverman, Khot, Lifshitz and Minzer, derived this from conjectures. Dinur, Khot, Perkins and Safra proved that, if a few vertices may be deleted, even independent sets of 1/9 of the vertices are hard to find, and Fei, Minzer and Wang’s route gives tiny independent sets, but only with an eight-coloring promise.

1:58The claim

Result 106 is one OpenAI preprint, 21 pages, dated September 24. For every fixed delta below 1/3, it gives a deterministic polynomial-time reduction from 3-SAT to graphs: satisfiable formulas give three-colorable graphs, and unsatisfiable formulas give graphs in which every independent set has fewer than delta times the number of vertices. Since a graph colored with c colors has an independent set of at least a c-th of its vertices, coloring three-colorable graphs with any fixed number of colors is NP-hard. That coloring consequence was already known through Fei, Minzer and Wang, and also follows from result 105. The new part is the independent-set bound under the full three-coloring promise, proved from ordinary label cover with no condition on the sizes of its projection fibers. OpenAI published a Lean formalization, 454 files and about 94,000 lines, self-contained. Its target is the reduction, including the size of the output graph. We found no unproved steps; we have not run the check.

3:12How the proof goes

The proof starts from label cover with perfect completeness and tiny value on unsatisfiable formulas, from the PCP theorem and parallel repetition. It builds chains of question tuples, replacing one question at a time. A vertex of the graph is a point, drawn by a finite random experiment, that assigns a phase on the circle to every possible answer of a tuple. Projections between answers link points at distance zero, and an edge joins x and y when x is within 1/8 of y shifted by half a turn. If the formula is satisfiable, evaluating every point at the satisfying answer gives each vertex one phase; adjacent vertices then get phases at least 3/8 apart, so three equal arcs of the circle color the graph properly. In our test of this rule on random phases, every edge got two different colors. For soundness, an independent set gives bounded functions on the phase spaces that flip sign under the half turn and obey a common Lipschitz bound. Austin’s junta theorem, a continuous counterpart of Friedgut’s, approximates such functions using a bounded number of answer coordinates, however many there are. The proof chooses such coordinate lists for whole stretches of a chain, with independent random rotations at every layer. If two separated stretches share an answer, that answer satisfies a label cover test in between, so low label cover value makes this rare. Two further steps turn this into a density bound. An alignment lemma, built from minimax, Ramsey-type homogenization and random arrays, lets each listed label, on most sampled sets of layers, be assigned one index shared by all its occurrences. Then coefficients are sampled at finitely many levels between zero and one, with geometrically decreasing probabilities, and a bound on influential coordinates gives a small mean square, hence a small independent set. Finally the random experiment is expanded exactly into unweighted vertices, so the reduction is deterministic.

5:18Where it stands

The preprint is not peer reviewed and has not been revised since its release. The Lean formalization covers the main theorem and proves its own inputs, with a Friedgut-type junta theorem in place of Austin’s; we have not run it. It is not among the papers OSVerify reviewed, and we have seen no expert review. The gap between the algorithms’ growing number of colors and hardness for every fixed number remains wide. If it holds, then unless P equals NP, even knowing that a graph is three-colorable does not make it easy to find an independent set holding any fixed fraction of its vertices.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.