TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-28

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 pure blockade with a perfect pattern has a large complete or anticomplete subblockade

Statement

Let $B = (B_{1}, \dots, B_{t})$ be a pure blockade whose pattern graph is perfect. Then $B$ has a complete or anticomplete subblockade of length at least $\sqrt{t}$ and of width at least the width of $B$ .

Facts & Assumptions

Given: A pure blockade $B = (B_{1}, \dots, B_{t})$ with perfect pattern graph $P (B)$ .

[L1]

In the pattern graph, two indices are adjacent exactly when the corresponding two blocks are complete to one another (The pattern graph of a pure blockade).

[L2]

Every perfect graph on $t$ vertices has a clique or stable set of size at least $\sqrt{t}$ (Every perfect graph has a clique or stable set of size at least the square root of its order).

[L3]

A complete subblockade is one whose block pairs are all complete, and an anticomplete subblockade is defined similarly (Complete, anticomplete, pure, weakly sparse, and $x$ -sparse blockades).

[L4]

The width of a blockade is the minimum size of one of its blocks, so discarding blocks cannot decrease the width bound inherited from the remaining blocks (Blockades, their length, their width, and their support).

Proof

technique · direct

1.1

Applying [L2] to the perfect pattern graph $P (B)$ , choose a set $I \subseteq [t]$ with $∣ I ∣ \geq \sqrt{t}$ that is either a clique or a stable set in $P (B)$ .

L2givenchoose

2.1

If $I$ is a clique, then [L1] says that every two blocks indexed by $I$ are complete to one another, so $(B_{i} : i \in I)$ is a complete subblockade in the sense of [L3]. If $I$ is a stable set, then no two indices in $I$ are adjacent in the pattern graph, so every two corresponding blocks are anticomplete and $(B_{i} : i \in I)$ is an anticomplete subblockade. In either case the width is at least that of $B$ by [L4].

step 1.1L1L3L4

3.1

Therefore $B$ has a complete or anticomplete subblockade of length at least $\sqrt{t}$ and width at least the original width.

step 2.1∎

Depends on

Used by

A pure blockade can have a perfect pattern that is not a cograph Example

Dependency tree · two levels

13 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, The Erdos-Hajnal Conjecture - A Survey, Theorem 1.3 (standard reference, not scraped)
Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdos-Hajnal for graphs with no 5-hole, Section 5 (standard reference, not scraped)