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 maximal pure blockade with large total $a$ -mass must already have at least $ϵ^{- 2}$ blocks

Statement

Let $ϵ \in (0, \frac{1}{2})$ , let $a \geq 1$ , and let $G$ be a graph with the property that every induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{2 a} ∣ G ∣$ contains a complete or anticomplete $(k, ∣ F ∣ / k^{a})$ -blockade for some $k \in [2, ϵ^{- 1}]$ .

Suppose $q$ is maximal subject to the existence of a pure blockade $(A_{1}, \dots, A_{q})$ in $G$ whose pattern graph is $P_{4}$ -free, such that $∣ A_{i} ∣ \geq ϵ^{3 a} ∣ G ∣$ for every $i$ and

$\sum_{i = 1}^{q} ∣ A_{i} ∣^{1 / a} \geq ∣ G ∣^{1 / a} .$

Then $q \geq ϵ^{- 2}$ .

Facts & Assumptions

Given: The hypotheses of the statement and a maximal blockade $(A_{1}, \dots, A_{q})$ .

Proof

technique · direct

1.1assume-contragiven

Suppose for contradiction that $q < ϵ^{- 2}$ . Reorder the blocks so that $∣ A_{1} ∣ = \max_{i} ∣ A_{i} ∣$ . Then $q ∣ A_{1} ∣^{1 / a} \geq \sum_{i = 1}^{q} ∣ A_{i} ∣^{1 / a} \geq ∣ G ∣^{1 / a},$ so $∣ A_{1} ∣ \geq ∣ G ∣ / q^{a} \geq ϵ^{2 a} ∣ G ∣$ . By the hypothesis on $G$ , the induced subgraph $G [A_{1}]$ contains a complete or anticomplete $(k, ∣ A_{1} ∣ / k^{a})$ -blockade $(B_{1}, \dots, B_{k})$ for some $k \in [2, ϵ^{- 1}]$ .

2.1step 1.1given

Replace the block $A_{1}$ by $B_{1}, \dots, B_{k}$ , and keep the other blocks $A_{2}, \dots, A_{q}$ . Because $(A_{1}, \dots, A_{q})$ was pure, every outside block is either complete or anticomplete to $A_{1}$ , hence to each $B_{j} \subseteq A_{1}$ . The new blockade is still pure, its pattern graph is obtained by substituting a complete or edgeless graph for the vertex corresponding to $A_{1}$ , and so it is still $P_{4}$ -free.

3.1step 2.1algebra

Every new block satisfies $∣ B_{j} ∣ \geq ∣ A_{1} ∣ / k^{a} \geq ϵ^{a} ∣ A_{1} ∣ \geq ϵ^{3 a} ∣ G ∣$ , while $\sum_{j = 1}^{k} ∣ B_{j} ∣^{1 / a} \geq k {(\frac{∣ A_{1} ∣}{k^{a}})}^{1 / a} = ∣ A_{1} ∣^{1 / a} .$ So the new blockade still satisfies the lower bound on every block and on the total $a$ -mass, but it has $q - 1 + k > q$ blocks. This contradicts the maximality of $q$ .

4.1discharge-contradictionstep 3.1∎

Therefore $q \geq ϵ^{- 2}$ .

Depends on

Used by

Complete or anticomplete blockade hypotheses force an ε-restricted induced subgraph Theorem

Dependency tree · two levels

5 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

Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path, Theorem 7.4 and Claim 7.4.1 (standard reference, not scraped)

A maximal pure blockade with large total aa-mass must already have at least ϵ−2ϵ−2 blocks