CorollaryStatement: AI-generatedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

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 linearly large induced subgraph of a graph with few induced copies again has a linearly large restricted set

Statement

Fix a graph $H$ , a real $ϵ \in (0, \frac{1}{2})$ , and a fraction $λ > 0$ . Then there exists $δ > 0$ such that whenever $G$ is a nonempty graph on $n$ vertices with ${ind}_{H} (G) < (δ n)^{∣ V (H) ∣}$ and $W \subseteq V (G)$ satisfies $∣ W ∣ \geq λ n$ , the induced subgraph $G [W]$ contains an $ϵ$ -restricted set of size at least $δ ∣ W ∣$ .

Facts & Assumptions

Given: A graph $H$ , a real $ϵ \in (0, \frac{1}{2})$ , and a real $λ > 0$ .

[L1]

If $G$ has $n$ vertices, $h = ∣ V (H) ∣$ , ${ind}_{H} (G) < (δ n)^{h}$ , and $∣ W ∣ \geq λ n > 0$ , then ${ind}_{H} (G [W]) < ((δ / λ) ∣ W ∣)^{h}$ (If $G$ has fewer than $(δ n)^{h}$ induced copies of $H$ and $∣ W ∣ \geq λ n$ , then $G [W]$ has fewer than $((δ / λ) ∣ W ∣)^{h}$ ).

[L2]

There is $δ_{0} > 0$ such that every nonempty graph $J$ with ${ind}_{H} (J) < (δ_{0} ∣ V (J) ∣)^{∣ V (H) ∣}$ has an $ϵ$ -restricted set of size at least $δ_{0} ∣ V (J) ∣$ (Nikiforov: for every $H$ and every $ϵ \in (0, \frac{1}{2})$ there is $δ > 0$ such that every graph $G$ with ${ind}_{H} (G) < (δ ∣ V (G) ∣)^{∣ V (H) ∣}$ has an $ϵ$ -restricted vertex set of size at least $δ ∣ V (G) ∣$ ).

Proof

technique · direct

1.1L2choosealgebra

Let $δ_{0}$ be the constant of [L2] for $H$ and $ϵ$ , and set $δ : = \min {δ_{0}, λ δ_{0}}$ . Then $δ > 0$ , $δ \leq δ_{0}$ , and $δ / λ \leq δ_{0}$ .

2.1step 1.1L1algebra

If ${ind}_{H} (G) < (δ n)^{∣ V (H) ∣}$ and $∣ W ∣ \geq λ n$ , then [L1] gives ${ind}_{H} (G [W]) < ((δ / λ) ∣ W ∣)^{∣ V (H) ∣} \leq (δ_{0} ∣ W ∣)^{∣ V (H) ∣}$ .

3.1step 1.1step 2.1L2algebra∎

Applying [L2] inside $G [W]$ yields an $ϵ$ -restricted set of size at least $δ_{0} ∣ W ∣$ . Since $δ_{0} ∣ W ∣ \geq δ ∣ W ∣$ by step 1.1, this is the required set.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

21 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.