Large independent sets in three-colorable graphs
Label Cover instances; a graph built from families of phases on layers of tuples of questions, with a proper coloring by three colors when all tests can be satisfied. Lipschitz functions for the sup distance on tori: odd extension, means over coordinates, influences. Lists of answers from an independent set, and the alignment theorem for families of lists, with proofs of the minimax theorem and of Ramsey's theorem. The theorem: for every delta > 0 it is NP-hard to tell graphs with a proper coloring by three colors from graphs whose independent sets have fewer than delta |V| vertices, from two named hypotheses (the PCP theorem and parallel repetition); Austin's theorem on Lipschitz functions of many variables, which the proof uses, is proved in the course Hypercontractivity on a torus and juntas for Lipschitz functions. The course is an exposition of OpenAI's proof (2026).
Six lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.
- Label Cover and the graph of the reduction
- Lipschitz functions on a torus: extension, juntas and influences
- From an independent set to lists of answers
- Alignment of lists: patterns, minimax and Ramsey's theorem
- Order-invariant arrays and the common index
- The coefficient test and the theorem
Theorems and assumptions · Reader and editable sources · Course record
Prerequisites
- Lipschitz functions are close to juntas (Hypercontractivity on a torus and juntas for Lipschitz functions)
- Projection games and the base game (2-to-1 games with perfect completeness)
- The lesson Projection games and the base game (course Two-to-one games with perfect completeness), for the Label Cover instances; the lesson Lipschitz functions are close to juntas (course Hypercontractivity on a torus and juntas for Lipschitz functions), for Theorem (J); the Lebesgue integral on a cube and Fubini's theorem (core course Measure and Integration).