TheoremStatement: 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.

Loglog quantitative induced density bound

Statement

For every nonempty finite graph $H$ there is $C_{H} > 0$ such that, for $0 < x < 1 / 2$ and $δ = 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)},$ every nonempty finite graph $G$ with ${ind}_{H} (G) \leq (δ ∣ G ∣)^{∣ H ∣}$ has a nonempty $S \subseteq V (G)$ of size at least $δ ∣ G ∣$ with $e (G [S]) \leq x (\binom{∣ S ∣}{2})$ or $e (\overline{G} [S]) \leq x (\binom{∣ S ∣}{2})$ . Every $H$ -free host qualifies. The strict few-copy version covers the null pattern vacuously.

Facts & Assumptions

Given: Nonempty $H, G$ , $0 < x < 1 / 2$ , and the copy hypothesis with the displayed fraction after $C_{H}$ is chosen.

[F1]

From Qid logarithmic and constant divisibility: Every nonempty finite graph $H$ is $ℓ$ -divisive for each of $ℓ (x) = \log_{2} (1 / x)$ and $ℓ (x) = 2$ . Both functions are subreciprocal on $(0, 1 / 2)$ .

[F2]

For nonempty $ℓ$ -divisive $H$ and subreciprocal $ℓ$ , some $C_{H, ℓ} > 0$ gives the fraction $δ = 2^{- C_{H, ℓ} \log_{2} (1 / ϵ)^{2} / \log_{2} ℓ (ϵ)}$ on $0 < ϵ < 1 / 2$ ; a nonempty host with at most $(δ ∣ G ∣)^{∣ H ∣}$ embeddings has the asserted nonempty sparse-or-dense set of size at least $δ ∣ G ∣$ . (Quantitative density theorem for ell divisive graphs).

Proof

1.1

Take $ℓ (x) = \log_{2} (1 / x)$ . The hypotheses on the function and on the nonempty $H$ required by [F2] hold by [F1]. Since $0 < x < 1 / 2$ , we have $ℓ (x) > 1$ and hence $\log_{2} ℓ (x) > 0$ . Substitution into [F2] gives exactly the displayed fraction and the required set, with $C_{H} = C_{H, ℓ}$ .

F1F2

2.1

An $H$ -free host has ${ind}_{H} (G) = 0 \leq (δ ∣ G ∣)^{∣ H ∣}$ . For null $H$ , there is exactly one induced embedding, the empty function; $(δ ∣ G ∣)^{0} = 1$ , so the strict inequality is impossible. This gives the stated boundary clauses without applying the formula at $x = 1 / 2$ .

step 1.1algebra∎

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 1.8; 5.1 and 5.2.

Depends on

Used by

Dependency tree · two levels

13 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)