VibeMathedMath problems solved with AI

The Erdős-Hajnal conjecture for paths: does every path PtP_t have the Erdős-Hajnal property?

A graph HH has the Erdős-Hajnal property if there is c=c(H)>0c=c(H)>0 such that every nn-vertex graph with no induced subgraph isomorphic to HH contains a clique or a stable set of size at least ncn^{c}. Erdős and Hajnal conjectured in 1977 that every graph HH has this property; the conjecture is open in general. This entry records the case of paths: does the path PtP_t on tt vertices have the Erdős-Hajnal property for every t≥1t\ge1? Before this work it was known for t≤5t\le5 (P5P_5 by Nguyen, Scott and Seymour, 2023), and for all tt only with the weaker bound 2(log⁡n)1−o(1)2^{(\log n)^{1-o(1)}} in place of ncn^{c}.

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI co-developed
Method
Argument
Field
Graph theory; induced subgraphs, Erdős-Hajnal conjecture
Posed by
Paul Erdős and András Hajnal (the general conjecture; paths are its special case)
Year posed
1977
Years open
49y
Solved
2026-10-17
Model
ChatGPT-6 Astra
Vendor
OpenAI
Collaborators
Tung H. Nguyen
Verification
Unreviewed
Publication
Preprint
Significance
42 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1 of arXiv:2610.24887 (Tung H. Nguyen, v1 17 October 2026): PtP_t has the Erdős-Hajnal property for every tt. Theorem 1.2 extends it to the trees S1,2,tS_{1,2,t} and the graphs S1,2,t′S'_{1,2,t}, which include the bull, E and the bird. This is not the general conjecture. Concurrent independent proofs of the path case: Yuwen Zhou's repository (public 8 October 2026, with a Lean development conditional on stated literature hypotheses and an anonymous P6P_6 project), later arXiv:2611.01963 (Huang, Zhou, Zhou; Claude Opus 5.5 and ChatGPT-6), and Google DeepMind's Cogentic manuscript with Lean (18 October). The first public proof of the path case may not be this one.

What the AI did

From the paper's Declaration of generative AI use: ChatGPT-6 Astra was mathematically involved in two subsections and one section; the ideas in the rest are the author's. Asked to prove a weaker version of a modular-decomposition lemma, Astra proved the full purity version; after discussions directed by the author it found the proof of the path-splitting lemma for r=5r=5, which the author extended to general rr; it also cleaned up the author's endpoint-switching argument. Astra assisted with proofreading and mathematical review; ChatGPT-6 Luna helped copy-edit and ChatGPT-6 Sol drew the figures.

Verification

No independent mathematician has checked this yet. Read by this site on 15 November 2026 in the TeX source of arXiv:2610.24887v2: the conjecture and Theorem 1.1 as stated in the introduction, the concurrent-work section and the AI declaration. The proof (39 pages) was not refereed here and there is no formal proof of this paper. Checked against the concurrent work: Zhou's GitHub repository was created 8 October 2026 (UTC), Nguyen's v1 posted 17 October, DeepMind's manuscript committed 18 October; DeepMind's README credits Nguyen as first to their knowledge. The catalog had no entry on this question.

Sources

Submitted by MellowGander562 on

Changelog2 changes

Discussion