LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09

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.

Special copy trichotomy produces a restricted blockade

Statement

For every nonempty finite graph $H$ there exist $k_{1}, k_{2} > 0$ such that, whenever $G$ is nonempty, $n = ∣ G ∣$ , $0 < x \leq 1 / (8 ∣ H ∣)$ and ${ind}_{H} (G) < x^{k_{1}} n^{∣ H ∣}$ , there is a QID $x$ -restricted sequence of length at least $2 \log_{2} (1 / x)$ and width at least $⌊ x^{k_{2}} n ⌋$ . At least half its indices form a sequence uniformly $x$ -sparse in $G$ or its complement, so that sequence has length at least $\log_{2} (1 / x)$ and the same width lower bound.

Facts & Assumptions

Given: A nonempty finite pattern $H$ . The host $G$ and $x$ obey the statement, with the copy threshold imposed after the constants are chosen.

[F1]

Given $H, g, α$ , the maximal-blowup trichotomy supplies constants $β, γ > 0$ for all hosts of order $n \geq 2$ and $0 < x \leq 1 / (8 ∣ H ∣)$ : a few- $(H - g)$ subset of size at least $x^{β} n$ , at least $x^{γ} n^{∣ H ∣}$ copies, or an $x$ -sparse pair with sizes at least $x^{β} n$ and $n / (2 ∣ H ∣)$ . (Qid maximal blowup trichotomy).

[F2]

QID sequences allow empty blocks. Restrictedness means that each later union is directionally sparse to its earlier block in one fixed graph or complement for that index. (Qid restricted blockade with empty blocks).

[F3]

For every real $y$ , its unique integer part satisfies $⌊ y ⌋ \leq y < ⌊ y ⌋ + 1$ . (Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

[F4]

$\log_{b} x = \frac{\log x}{\log b}, b^{\log_{b} x} = x, \log_{b} (b^{u}) = u (u \in R)$ . (Change of base and inversion of the positive-base real exponential).

Proof

1.1

Induct on $h = ∣ H ∣$ . If $h = 1$ , take $k_{1} = k_{2} = 1$ ; the premise $n < x n$ is impossible. For $h \geq 2$ , fix $g \in V (H)$ and let $k_{1}^{'}, k_{2}^{'}$ be the constants for $H - g$ . Apply [F1] with $α = k_{1}^{'}$ to obtain $β, γ$ . Set $d_{0} = \log_{2} (2 h) > 0$ , $k_{1} = γ + 2 d_{0} h$ , and $k_{2} = k_{2}^{'} + β + 2 d_{0}$ .

baseihF1

2.1

If $x^{k_{2}} n < 1$ , take $- ⌊ - 2 \log_{2} (1 / x) ⌋$ empty blocks. By [F3] this integer is at least the required length, and the width is $0 = ⌊ x^{k_{2}} n ⌋$ . All degree conditions hold by [F2]. Hence assume $x^{k_{2}} n \geq 1$ .

F2F3step 1.1

3.1

Consider nonempty restricted sequences $(B_{1}, \dots, B_{k})$ whose first $k - 1$ blocks have size at least $x^{k_{2}} n$ and whose last block has size at least $(2 h)^{1 - k} n$ . The one-block sequence $V (G)$ qualifies. All these sequences have length at most $n$ , so a maximum length is attained in a finite nonempty family. Fix such a sequence. If $k - 1 \geq 2 \log_{2} (1 / x)$ , its first $k - 1$ blocks prove the restricted assertion. Otherwise [F4] gives $∣ B_{k} ∣ \geq 2^{(1 - k) d_{0}} n > x^{2 d_{0}} n \geq x^{2 d_{0} - k_{2}} > 1$ . Thus $∣ B_{k} ∣ \geq 2$ .

F4step 2.1algebra

4.1

Apply [F1] inside $G [B_{k}]$ at $x$ with $α = k_{1}^{'}$ . Its count outcome would give ${ind}_{H} (G) \geq {ind}_{H} (G [B_{k}]) \geq x^{γ} ∣ B_{k} ∣^{h} > x^{γ + 2 d_{0} h} n^{h} = x^{k_{1}} n^{h}$ , contrary to the premise; the first inequality holds by inclusion of the embedding sets. Its sparse-pair outcome would replace $B_{k}$ by $A, B$ with $∣ A ∣ \geq x^{β} ∣ B_{k} ∣ > x^{β + 2 d_{0}} n \geq x^{k_{2}} n$ and $∣ B ∣ \geq ∣ B_{k} ∣ / (2 h) \geq (2 h)^{- k} n$ . Earlier degree conditions persist because their target blocks are unchanged and their later vertices are restricted. The new pair meets the last condition, contradicting maximum length.

F1step 1.1step 3.1

5.1

Therefore [F1] supplies $A \subseteq B_{k}$ with $∣ A ∣ \geq x^{β} ∣ B_{k} ∣ > x^{β + 2 d_{0}} n$ and ${ind}_{H - g} (G [A]) < x^{k_{1}^{'}} ∣ A ∣^{h - 1}$ . Here $A$ is nonempty and $x \leq 1 / (8 h) \leq 1 / (8 (h - 1))$ , so induction applies. It gives length at least $2 \log_{2} (1 / x)$ and width at least $⌊ x^{k_{2}^{'}} ∣ A ∣ ⌋ \geq ⌊ x^{k_{2}^{'} + β + 2 d_{0}} n ⌋ = ⌊ x^{k_{2}} n ⌋$ . Floor monotonicity follows from [F3]: if $u \leq v$ and $⌊ u ⌋ > ⌊ v ⌋$ , then $u \geq ⌊ v ⌋ + 1 > v$ . This completes the restricted-sequence induction.

F1F3step 1.1step 4.1induction

6.1

In the resulting sequence assign an index to $I$ if its later union is $x$ -sparse to its block in $G$ , and to $J$ otherwise. Restrictedness ensures the latter indices use $\overline{G}$ ; the last index can be assigned to $I$ because its tail is empty. One of the two sets has at least half the indices. Retain its blocks in their old order. Each later union has only shrunk, so its degree inequalities remain true, and each retained block has its old size. This proves the uniform conclusion.

F2step 1.1step 5.1algebradischarge-induction∎

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 4.4; 2.3.

Depends on

Used by

Dependency tree · two levels

41 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

Bucic, Nguyen, Scott and Seymour, Induced subgraph density I (standard reference, not scraped)