[#P43] Erdős-Hajnal conjecture
Problem. For every finite graph \(H\), there exists \(c(H)>0\) such that every \(H\)-free graph on \(n\) vertices contains a clique or an independent set of size at least \(n^{c(H)}\), where \(H\)-free means having no induced copy of \(H\).
1Context
Forbidding one induced pattern is conjectured to improve the logarithmic homogeneous sets supplied by general Ramsey theory to polynomial size.
2Problem setup
Definition 1 (An induced copy preserves both edges and nonedges among its selected vertices). An induced copy preserves both edges and nonedges among its selected vertices.
Definition 2 (A clique has every possible edge, while an independent set has none). A clique has every possible edge, while an independent set has none.
Remark 1. Forbidding one induced pattern is conjectured to improve the logarithmic homogeneous sets supplied by general Ramsey theory to polynomial size.
3What counts as a solution
- Prove the polynomial-size homogeneous-set bound for every fixed forbidden induced graph H, or give a fixed H and an infinite family of H-free graphs whose largest cliques and independent sets are smaller than n^c for every positive c.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: Huang, Ju, and Zhou prove the Erdős-Hajnal property for the E-graph and Bird forbidden-induced-subgraph classes, extending recent five-vertex-path and bull cases. The assertion for every fixed H remains open. Exact unresolved remainder: Prove a polynomial-size clique or independent set for every fixed forbidden induced graph H, or give one fixed H and an H-free family violating every positive power bound.[1]
1Records
Notes and companion material
Original intake status. The cited 2026 paper proves new cases of the Erdős-Hajnal conjecture while treating the general assertion as open. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- The conjecture is now known for every graph H on at most five vertices and for further special families.
Computational notes
- Finite graph searches can verify fixed H and bounded n without establishing an asymptotic exponent.
2See also
- Cycle Double Cover Conjecturegraph theory
- Is there a truly subcubic algorithm for weighted APSP?graph theory
- The Total Coloring Conjecturegraph theory
How to cite
TheoremDB contributors, “Erdős-Hajnal conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/erdos-hajnal-conjectureThis page as plain text: erdos-hajnal-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from arxiv.org[1], current as of July 31, 2026.
1References
- Packet source. Shenwei Huang, Yiao Ju, and Yidong Zhou, “Erdős-Hajnal beyond the five-vertex path”. arXiv:2606.06258 (2026). Shenwei Huang, Yiao Ju, and Yidong Zhou, arXiv:2606.06258, abstract. ↗preprint · primary source · arXiv:2606.06258, checked 2026-07-31 · checked 2026-07-31Source use: original summary.The cited 2026 paper proves new cases of the Erdős-Hajnal conjecture while treating the general assertion as open. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at abstract and main theorems for the E-graph and Bird.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Adds two current special cases while leaving the universal forbidden-graph statement open.Source named by the research packet.
An original CC0 restatement prepared by TheoremDB maintainers.