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.

Few induced copies exclude a fixed labelled blowup

Statement

Let $J$ be nonempty with $j = ∣ J ∣$ , and $t \geq 1$ an integer. If ${ind}_{J} (G) < (t / j)^{j}$ , no $(t, 1 / j)$ -blowup of $J$ exists in $G$ .

Facts & Assumptions

Given: A nonempty $j$ -vertex graph $J$ , integer $t \geq 1$ , and ${ind}_{J} (G) < (t / j)^{j}$ .

[F1]

From Good copy extension count: Every good embedding of $J [I]$ , $I \subseteq V (J)$ , has at least $(t / j)^{j - ∣ I ∣}$ good extensions to $J$ .

Proof

1.1

Suppose such a blowup exists. Its unique empty good embedding has at least $(t / j)^{j}$ good full extensions by [F1] with $I = \emptyset$ .

assume-contraF1

2.1

Every good extension is an induced embedding, so ${ind}_{J} (G) \geq (t / j)^{j}$ , contradicting the strict hypothesis. Therefore the blowup cannot exist.

step 1.1discharge-contradiction∎

Source notes

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

Depends on

Used by

Local special copy trichotomy Lemma
Qid maximal blowup trichotomy Lemma
Special copy trichotomy produces a restricted blockade 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

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