--- id: "2026-09-16-chvatal-conjecture-proved" url: "https://postcutoff.com/e/2026-09-16-chvatal-conjecture-proved/" as_of: "2026-11-19T22:11:00+01:00" date: "2026-09-16" date_precision: day category: science importance: 4 confidence: high status: [Result confirmed] verification: Lean-verified sources: 4 editor: human editor human_review: null version: "2026-10-07" --- As of: 2026-11-19 22:11 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-09-16-chvatal-conjecture-proved/ # Chvátal's 1972 conjecture proved (Chang–Liu–Liu, ChatGPT-assisted), then a GPT-6 Astra 'proof from The Book' and a Codex-built Lean formalization On Sept 16, 2026 Fan Chang, Hong Liu and Miao Liu posted a proof of Chvátal's conjecture (1972): every hereditary family of sets has a largest intersecting subfamily that is a star. It went through a sharp correlation inequality for increasing Boolean functions. ChatGPT tested candidate inequalities and proved a special case that pointed the authors to the general theorem. Within days the proof was formalised in Lean with GPT-6 via Codex. On Sept 23 Ellis, Filmus and Friedgut posted a 7-page spectral "proof from The Book" that GPT-6 Astra produced after reading the Chang–Liu–Liu manuscript. ## Key facts - arXiv 2609.19123 (Sept 16, 2026), Chang, Liu & Liu: proves Chvátal's conjecture and the Friedgut–Kahn–Kalai–Keller correlation form Cov(f,g) ≥ ¼ min_i Inf_i[f] for antipodal g - AI disclosure (Chang–Liu–Liu): 'We used ChatGPT to test candidate inequalities… ChatGPT proved the special case of the inequality in Theorem 1.2 when f is a symmetric threshold function, inspiring the authors to pursue and ultimately prove the stronger inequality'; all proofs written and checked by the authors - Lean: boonsuan/chvatal formalizes the Chang–Liu–Liu proof, 'generated with GPT-6 through Codex'; registered with Palomar as PALOMAR-2026-09-17-000004; no sorry or extra axioms in the library; also imported into Lean Pool (PR #443) - arXiv 2609.28404 (Sept 23), Ellis, Filmus & Friedgut, 'Chvátal's conjecture: a proof from The Book': a short direct spectral proof plus a projection-packing-number strengthening - Their AI chronology: weeks of failed attempts with ChatGPT-6 Astra and Claude Fable 5.1 on their own conjectures (H, I); after they fed in the Chang–Liu–Liu paper, Astra announced a proof that the projection packing number is tight for every downset, then 'stripped [it] down to the spectral bare bones'; ChatGPT used only for proofreading of the final paper ## What happened Chvátal's conjecture, posed in 1972, is one of the best-known open problems in extremal set theory. Chang, Liu and Liu (IBS) proved it through a sharp correlation inequality for increasing Boolean functions, and they credit ChatGPT with proving a special case that showed them the way. A Lean formalization made with GPT-6 in Codex appeared the next day in the Palomar registry. A week later, Ellis, Filmus and Friedgut described how GPT-6 Astra had failed for weeks on their related conjectures. Once given the new paper, it produced a short spectral proof, which they present as "a proof from The Book". ## Why it matters It is a clear example of the late-2026 pattern in mathematics. A human-led breakthrough with model assistance is followed within days by AI simplification and AI formalization. Disclosures are now detailed enough to separate the contribution of each model. ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): 108 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 78 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 169 days after its cutoff - Grok 4.7 (training cutoff May 2026): 108 days after its cutoff ## Sources 1. [arXiv 2609.19123: A proof of Chvátal's conjecture via a sharp correlation inequality](https://arxiv.org/abs/2609.19123) (arxiv.org, paper) 2. [arXiv 2609.28404: Chvátal's conjecture, a proof from The Book (Ellis, Filmus, Friedgut)](https://arxiv.org/abs/2609.28404) (arxiv.org, paper) 3. [GitHub boonsuan/chvatal: Lean formalization generated with GPT-6 through Codex](https://github.com/boonsuan/chvatal) (github.com, code) 4. [Lean Pool PR #443: import Chvátal's conjecture and sharp Boolean correlation](https://github.com/Vilin97/lean-pool/pull/443) (github.com, code) ## Changes - 2026-10-07: Science block: short label for the open-problems table - 2026-10-01 (filed): Created ## Related - 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md) - 2026-09-26: [GPT-6 Astra finds a proof improving the Kővári–Sós–Turán bound](https://postcutoff.com/e/2026-09-26-mubayi-zarankiewicz-astra/index.md) - 2026-09-21: [Lean Pool: an AI-maintained archive of Lean formalizations grows past 3 million lines](https://postcutoff.com/e/2026-09-21-lean-pool-ai-maintained-formal-math-archive/index.md) - 2026-08-18: [Palomar launches: a registry of Lean-verified mathematics to curb misrepresented AI proof claims](https://postcutoff.com/e/2026-08-18-palomar-lean-registry/index.md)