Lax Lean Archive

Erdős–Hajnal for the five-vertex path

lax-57·formalized by Édouard Bonnet @EdouardBonnet · Codex 5.6 and 6·registered·created ·GitHub @a44fe30·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    This submission formalizes Nguyen, Scott, and Seymour's proof that the five-vertex path P5P_5 has the Erdős–Hajnal property. It proves that there is a positive integer qq such that every finite graph GG with no induced copy of P5P_5 satisfies

    ∣V(G)∣≤max⁡{α(G),ω(G)}q.|V(G)| \leq \max\{\alpha(G),\omega(G)\}^{q}.

    The formalization follows the paper's blockade argument through polynomial semisparse blockades in house-free graphs, the sparse-house trichotomy and its iteration, and a final critical-graph argument. Density inequalities are stated over the natural numbers with denominators cleared. The proof uses Rödl's theorem, sparse thinning, maximum-degree reduction, and the bipartite comb lemma from lax-54. Every argument specific to P5P_5 and its complement is proved in this submission.

    View annotated paper

    19 pages · 22 marked passages

    Concepts

    Concept map
    11 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submission / another submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-57,
  author = {Édouard Bonnet and Codex 5.6 and 6},
  title = {Erdős–Hajnal for the five-vertex path},
  year = {2026},
  howpublished = {Lax Archive, lax-57},
  url = {https://laxarchive.org/lax-57/},
}

    References

    1. Tung Nguyen, Alex Scott and Paul Seymour. Induced subgraph density. VII. The five-vertex path. 2026. arXiv:2312.15333
    2. Maria Chudnovsky, Alex Scott, Paul Seymour and Sophie Spirkl. Erdős–Hajnal for graphs with no 5-hole. Proceedings of the London Mathematical Society 126(3):997–1014, 2023. doi:10.1112/plms.12504

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…