LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-27

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A $P_{4}$ -free graph on $q$ vertices has a homogeneous set of size at least $\sqrt{q}$

Statement

If $J$ is a $P_{4}$ -free finite graph with $q$ vertices, then

$hom (J) \geq \sqrt{q} .$

Facts & Assumptions

Given: A $P_{4}$ -free graph $J$ on $q$ vertices.

[L1]

Every $P_{4}$ -free graph with more than one vertex admits a partition $V (J) = A ⊔ B$ with $A, B \neq \emptyset$ such that $(A, B)$ is a pure pair (Chudnovsky--Scott--Seymour--Spirkl, "Erdos-Hajnal for graphs with no 5-hole", §5 Blockades, sentence immediately preceding Theorem 5.1).

Proof

technique · direct

1.1given

We prove the stronger inequality. [given] $α (J) ω (J) \geq q$ by induction on $q$ . The cases $q = 0$ and $q = 1$ are immediate.

2.1step 1.1L1

Assume $q \geq 2$ . By [L1], write $V (J) = A ⊔ B$ with $A, B \neq \emptyset$ and $(A, B)$ pure. Put. [step 1.1, L1] $a = α (J [A]), b = α (J [B]), c = ω (J [A]), d = ω (J [B]) .$ The induction hypothesis gives $a c \geq ∣ A ∣$ and $b d \geq ∣ B ∣$ .

3.1step 2.1algebra

If $(A, B)$ is complete, then. [step 2.1, algebra] $ω (J) = c + d$ and $α (J) = \max {a, b}$ , whence $α (J) ω (J) = \max {a, b} (c + d) \geq a c + b d \geq ∣ A ∣ + ∣ B ∣ = q .$ If $(A, B)$ is anticomplete, then $α (J) = a + b$ and $ω (J) = \max {c, d}$ , and the same calculation gives $α (J) ω (J) \geq a c + b d \geq q$ .

4.1step 1.1step 3.1algebra∎

The induction closes. Since. [step 1.1, step 3.1, algebra] $\max {α (J), ω (J)} \geq \sqrt{α (J) ω (J)}$ , one obtains $hom (J) \geq \sqrt{q}$ .

Depends on

Used by

Pure blockades with P₄-free patterns contain complete or anticomplete subblockades of square-root length Lemma

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdős-Hajnal for graphs with no 5-hole, §5 (standard reference, not scraped)

A P4P4​-free graph on qq vertices has a homogeneous set of size at least qq​