LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-04

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 complete-or-weakly-sparse blockade can be thinned to equal subblocks with directional sparsity

Statement

Let $a \geq 0$ , let $ϵ \in (0, \frac{1}{4}]$ , and let

$A = (A_{1}, \dots, A_{ℓ})$

be a blockade in a graph $G$ with $ℓ = ⌈ ϵ^{- 1} ⌉$ and width at least $m > 0$ . Assume that every distinct pair $(A_{i}, A_{j})$ is either complete or weakly $ϵ^{a}$ -sparse. Then there is a subblockade

$D = (D_{1}, \dots, D_{ℓ})$

such that:

$D_{i} \subseteq A_{i}$ and $∣ D_{i} ∣ = ⌈ ϵ ⌈ m ⌉ ⌉$ for every $i \in [ℓ]$ ;
if $(A_{i}, A_{j})$ is complete, then $(D_{i}, D_{j})$ is complete; and
if $(A_{i}, A_{j})$ is weakly $ϵ^{a}$ -sparse, then $D_{i}$ is $ϵ^{a - 5}$ -sparse to $D_{j}$ and $D_{j}$ is $ϵ^{a - 5}$ -sparse to $D_{i}$ .

Facts & Assumptions

Given: The blockade $A = (A_{1}, \dots, A_{ℓ})$ with $ℓ = ⌈ ϵ^{- 1} ⌉$ , width at least $m$ , and the complete or weakly $ϵ^{a}$ -sparse hypothesis on each distinct pair of blocks.

[L1]

A weakly $c$ -sparse ordered pair $(X, Y)$ satisfies $e_{G} (X, Y) \leq c ∣ X ∣ ∣ Y ∣$ by definition (Sparsity of one vertex set to another, and weak sparsity of a pair).

[L2]

A complete pair stays complete after passing to subsets (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

[L3]

Expectation is linear for finite families of random variables, without an independence hypothesis (Expectation is linear for every finite family of random variables, without any independence hypothesis).

[L4]

The probability of a finite union of events is at most the sum of their probabilities (The finite union bound).

Proof

Proof technique: use finite averaging to choose equal ambient blocks with controlled edge counts, then delete vertices that are too heavy against the chosen ambient blocks.

1.1

Put $n : = ⌈ m ⌉$ and $s : = ⌈ ϵ n ⌉$ . Since every $∣ A_{i} ∣$ is an integer at least $m$ , one has $n \leq ∣ A_{i} ∣$ . Choose independently and uniformly an $n$ -element subset $X_{i} \subseteq A_{i}$ for each $i$ . For a weakly $ϵ^{a}$ -sparse pair $(A_{i}, A_{j})$ , finite double counting and [L3] give $E e_{G} (X_{i}, X_{j}) = e_{G} (A_{i}, A_{j}) \frac{n^{2}}{∣ A_{i} ∣ ∣ A_{j} ∣} \leq ϵ^{a} n^{2} .$ Consequently the probability that $e_{G} (X_{i}, X_{j}) > ϵ^{a - 2} n^{2}$ is less than $ϵ^{2}$ : on that event the nonnegative edge count already exceeds the threshold, so its expectation is greater than the threshold times the event probability. There are at most $(\binom{ℓ}{2})$ relevant pairs, and $(\binom{ℓ}{2}) ϵ^{2} < \frac{1 + ϵ}{2} < 1$ because $ℓ = ⌈ ϵ^{- 1} ⌉ < ϵ^{- 1} + 1$ . By [L4], some simultaneous choice of the $X_{i}$ therefore satisfies $e_{G} (X_{i}, X_{j}) \leq ϵ^{a - 2} n^{2}$ for every weakly sparse pair. Complete pairs remain complete by [L2]. Fix such a choice.

givenL1L2L3L4choosealgebra

2.1

We choose $D_{1}, \dots, D_{ℓ}$ successively, always requiring $D_{i} \subseteq X_{i}$ and $∣ D_{i} ∣ = s$ . Suppose that $D_{1}, \dots, D_{i - 1}$ have already been chosen. For each $p \neq i$ with $(A_{p}, A_{i})$ weakly $ϵ^{a}$ -sparse, let $C_{p} \subseteq X_{i}$ consist of the vertices having more than $ϵ^{a - 4} n$ neighbours in $D_{p}$ when $p < i$ , or more than $ϵ^{a - 4} n$ neighbours in $X_{p}$ when $p > i$ . In either case step 1.1 gives $e_{G} (X_{i}, D_{p}) \leq e_{G} (X_{i}, X_{p}) \leq ϵ^{a - 2} n^{2},$ so $∣ C_{p} ∣ < ϵ^{2} n$ . Since $ℓ - 1 < ϵ^{- 1}$ , the union of the forbidden sets has fewer than $ϵ n$ vertices and therefore at most $s - 1$ vertices. Thus at least $n - s + 1 \geq s$ vertices survive: indeed $s \leq ⌈ n / 4 ⌉$ and $2 ⌈ n / 4 ⌉ \leq n + 1$ . Choose $D_{i}$ to be any $s$ survivors.

step 1.1L1choosealgebra

3.1

Let $(A_{i}, A_{j})$ be weakly $ϵ^{a}$ -sparse, and assume $i < j$ . When $D_{i}$ was chosen, the index $j$ was still future, so every vertex of $D_{i}$ has at most $ϵ^{a - 4} n$ neighbours in $X_{j}$ , hence at most that many in $D_{j}$ . When $D_{j}$ was chosen, every vertex of $D_{j}$ was required to have at most $ϵ^{a - 4} n$ neighbours in $D_{i}$ . Since $s \geq ϵ n$ , $ϵ^{a - 4} n \leq ϵ^{a - 5} s .$ Therefore $D_{i}$ is $ϵ^{a - 5}$ -sparse to $D_{j}$ and $D_{j}$ is $ϵ^{a - 5}$ -sparse to $D_{i}$ .

step 2.1algebra

4.1

If $(A_{i}, A_{j})$ is complete, then $(D_{i}, D_{j})$ is complete by [L2] because $D_{i} \subseteq A_{i}$ and $D_{j} \subseteq A_{j}$ . Together with step 3.1, this proves that $D = (D_{1}, \dots, D_{ℓ})$ has all the required properties. ∎

Depends on

Used by

Dependency tree · two levels

14 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdos-Hajnal beyond the five-vertex path, Lemma 2.6 (standard reference, not scraped)
Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path, Claim 7.1.1 (standard reference, not scraped)