Erdős–Hajnal for long induced paths: polynomial homogeneous sets in P_k-free graphs for every k
P_5 needed a new sparsification framework, P_6 is claimed with a method its authors say stops there, and the quasi-polynomial bound for all paths shows the target is near; so 69, just below even-order Chowla (70) and below diagonal Ramsey (78). Application value 5 is indirect. Leverage 38: paths are the key test family for the full Erdős–Hajnal conjecture.
The problem
A network that avoids one small pattern must contain a big group of mutual friends or mutual strangers. Prove it when the pattern is a long path.
- 1Forbid one small pattern H in a network
- 2Ramsey only promises about log n
- 3Conjecture: a power of n is guaranteed
- 4Proved up to 5 vertices; long paths open
The conjecture. The Erdős–Hajnal conjecture asserts that for every graph there is a constant such that every -vertex graph with no copy of has a clique or a stable (independent) set of size at least . Here means the copy uses edges and non-edges exactly as in . By comparison, Ramsey theory alone guarantees a clique or stable set of size only about for general graphs; the conjecture says that forbidding any single gives polynomial size. The conjecture was posed in 1977.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- Erdős–Hajnal for long induced paths: polynomial homogeneous sets in P_k-free graphs for every kThe problem
State of the art
Open for k ≥ 7; P_6 claimed but unrefereed. Nguyen, Scott and Seymour proved that every P_k-free graph has a homogeneous set of size (arXiv:2307.15032), and proved the conjecture for P_5 (arXiv:2312.15333, Proc. LMS 2026), which completes all five-vertex graphs. Huang, Ju and Zhou (arXiv:2606.06258, preprint) generalized the iterative-sparsification framework and proved the conjecture for two new six-vertex graphs (the E-graph and the bird graph), recovering P_5 and the bull. On 27 September 2026 a repository produced by Claude Opus 5.5 (github.com/machine-qed/erdos-hajnal-six-vertex-path) posted a 24-page proof for P_6 with a Lean 4 formalization that assumes three refereed imported theorems; it is unrefereed and states that the method does not extend to P_7. Nguyen (arXiv:2510.05724) proved that every P_5-free graph G has at most α(G)ω(G)^d vertices, so its fractional chromatic number is polynomial in its clique number. For general H the best bound remains (Erdős–Hajnal 1989). Many six-vertex graphs besides P_6 remain open.
Realistic applications
None directly. Polynomial homogeneous sets in P_k-free graphs would feed structural graph theory and algorithms for graph classes with forbidden induced paths (colouring, independent set).
What counts as solved
A refereed proof that for every k (or for k = 7) there is c_k > 0 such that every P_k-free graph on n vertices has a clique or stable set of size n^(c_k). Verification of the P_6 claim is partial progress.
How it gets verified
Lean proofA formal proof checked by Lean 4 / Mathlib.
Statement: the Erdős–Hajnal conjecture is Erdos61.erdos_61 in ErdosProblems/61.lean (Formal Conjectures pinned at commit e754a78 (17 October 2026)), stated for every graph H with IsErdosHajnalLowerBound H (fun n => n ^ c); the same file states the solved path case as erdos_61.variants.p5 with H = pathGraph 5. The target here is the same statement with pathGraph k for k = 6, 7 or for every k, which is a direct substitution into that definition. Accept a Lean proof that compiles against the pinned corpus and passes Comparator against the substituted statement; a verified P_6 proof counts as partial progress.
Claims under verification
+ add a claimWhere the work is
New structural arguments are needed; formal proofs (as for P_5 and P_6) and computer case analysis are small shares.
Bottlenecks
ranked by votes- #1TheoryFrom quasi-polynomial to polynomial
The density-increment arguments for long paths lose a factor at each of about log n steps; a polynomial bound needs an increment that does not degrade with path length.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Sep 27, 2026Claimed proof for P_6 (unrefereed)source
AI-produced paper with a Lean formalization; says the method stops at P_7.
- Dec 23, 2023The five-vertex pathsource
Completes the conjecture for all five-vertex graphs.
- Jul 27, 2023All paths approach Erdős–Hajnalsource
Quasi-polynomial homogeneous sets in P_k-free graphs.