Erdős–Hajnal conjecture: does an excluded induced $H$ force a polynomial clique or independent set? (Erdős #61)
Statement
The Erdős–Hajnal conjecture. For every fixed graph $H$, is there a constant $c=c(H)>0$ such that every graph $G$ on $n$ vertices containing no induced copy of $H$ has a clique or an independent set on at least $n^{c}$ vertices? Without the $H$-free hypothesis, arbitrary graphs guarantee only a homogeneous set of size $\Theta(\log n)$ by Ramsey's theorem, so the conjecture asserts that forbidding any one fixed induced subgraph boosts this to a polynomial $n^{c}$.
Acceptance. FULLY RESOLVES: a complete proof of the conjecture for all graphs $H$ — for every $H$ a constant $c(H)>0$ together with a proof that every $H$-free $n$-vertex graph has a clique or independent set of size $\geq n^{c(H)}$. A machine-checkable proof (Lean/Coq) is preferred, otherwise a full written proof. ADVANCES: (a) prove the conjecture for a new graph $H$ not currently covered (for instance a specific graph on $\geq 6$ vertices not reducible by substitution to a known case), with proof; (b) improve the general lower bound strictly beyond the best stated in the background (currently $\exp(c_H\sqrt{\log n\,\log\log n})$ for all $H$, and $2^{(\log n)^{1-o(1)}}$ for paths), with proof; (c) prove a new closure or reduction operation that enlarges the family of graphs for which the conjecture is known. Deliver the proof file.
Background
Conjectured by Erdős and Hajnal [ErHa89], who proved that every $H$-free graph on $n$ vertices contains a clique or independent set on $\geq \exp(c_H\sqrt{\log n})$ vertices for some $c_H>0$. Bucić, Nguyen, Scott, and Seymour [BNSS23] improved this general bound to $\geq \exp(c_H\sqrt{\log n\,\log\log n})$. The full conjecture is proved for: all $H$ on $\leq 4$ vertices (Erdős–Hajnal [ErHa89]); the $5$-vertex 'bull' (Chudnovsky–Safra [ChSa08]); the $5$-cycle $C_5$ (Chudnovsky, Scott, Seymour, and Spirkl [CSSS23]); and the path $P_5$ (Nguyen, Scott, and Seymour [NSS26]). Since Alon, Pach, and Solymosi [APS01] showed the family of graphs for which the conjecture holds is closed under vertex substitution, it is now known for every $H$ on $5$ vertices. When $H$ is any path, Nguyen, Scott, and Seymour [NSS24] obtained the near-polynomial bound $\geq 2^{(\log n)^{1-o(1)}}$. Catalogued as #80 in the Extremal Graph Theory problem collection. No cash prize is attached. Listed as open on erdosproblems.com/61 (fetched 2026-07-13, status 'open', tagged 'graph theory'); a Lean formalisation exists (google-deepmind/formal-conjectures, 61.lean). The attacker's tool: deep structural graph theory — induced-subgraph structure theorems and Ramsey-type counting; a realistic advance proves a new specific $H$ or sharpens the general lower bound, not a finite computation.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #61 (T. F. Bloom) | website |
| REF-02 | Lean formalisation — google-deepmind/formal-conjectures (Erdős #61) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.