Erdős–Hajnal conjecture proved for every path P_t

Your AI and this story

Key facts

• Paper: ‘Erdős–Hajnal for excluding paths’, Tung H. Nguyen (Titchmarsh Research Fellow, Oxford), arXiv 2610.24887 [math.CO], 17 Oct 2026. Theorem 1.2: ‘P_t has the Erdős–Hajnal property for all t ≥ 1.’ Theorem 1.3 extends it to the subdivided claws S_{1,2,t} and S’_{1,2,t} (covering the bull, E and the bird)
• Conjecture (Erdős and Hajnal, 1977): for every graph H there is b with every H-free graph G having a clique or stable set of size |G|^(1/b). It remains open in general
• New ingredient (abstract): ‘a novel Gyárfás path argument based on the ideas of bookkeeping blockades and splitting paths’
• AI declaration, verbatim: ‘ChatGPT-6 Astra was mathematically involved in Subsections 3.3 and 4.1 and Section B; the ideas in the rest of this paper are entirely due to the author.’ The author asked Astra for a weaker version of Lemma B.2 and ‘Astra then succeeded in proving the full purity version’; after discussions directed by the author, ‘Astra discovered a proof of Lemma 3.9 for r = 5’, which the author extended to all r; Subsection 4.1 was ‘cleaned up by Astra’. Writing by the author with copy-editing from ChatGPT-6 Luna; figures by ChatGPT-6 Sol
• Google DeepMind (concurrent work section): a team ‘including Junehyuk Jung, Joonkyung Lee, Thang Luong, and Aranyak Mehta’ told the author that ‘a DeepMind internal model had produced a proof of the Erdős–Hajnal property of P6; the proof was verified by Joonkyung Lee and accompanied by a Lean formalisation’. They then ‘obtained further results including the P_t case’. The Google team will post its AI-generated manuscript and Lean proof on GitHub rather than arXiv, ‘since they want to ensure that their material on the arXiv meets the standards of the mathematical community’. ‘At the time of submission, neither team had seen the other’s manuscript’
• Claude manuscripts named in the paper: ‘an anonymous GitHub repository contains an AI-generated manuscript claiming to prove the Erdős–Hajnal property of P6, produced by Claude Opus 5.5; and another GitHub repository by Yuwen Zhou contains a manuscript claiming to prove Theorem 1.2 (also available on Zenodo), assisted by Claude Opus 5.5 … We are not aware of independent expert reviews of either manuscript’
• The P6 repository is machine-qed/erdos-hajnal-six-vertex-path (created 27 Sep 2026): a 24-page paper plus Lean 4, ‘produced by Claude Opus 5.5 (Anthropic) and has not been refereed’; it proves a polynomial Rödl property with τ < 10^−15, not computed numerically
• Yuwen Zhou (UBC Okanagan), OctopusTide/erdos-hajnal-all-paths (created 8 Oct 2026, Zenodo DOI 10.5281/zenodo.23270286): the Lean main theorem AllPathsLocal.eh_all_paths takes three hypotheses (hRodl, a combinatorial lemma hcomb and EH for P6), so the formal statement is conditional on inputs supplied as assumptions, as the README shows