Pipeline-generated

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.

Quantitative Induced Density and the Log-Log Step: Examples

1 · Prerequisites

2 · Summary

These computations distinguish good copies from all labelled induced embeddings, evaluate the constant and logarithmic divisibility functions at $x = 1 / 16$ , and compare the two density losses with distinct symbolic constants. The numerical fractions illustrate the formulas; they do not certify numerical theorem constants for an arbitrary forbidden graph.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09Open item page →

A labelled blowup and its good copies

Example

Label $P_{3}$ by $1, 2, 3$ , with edges $12, 23$ . Let $A_{i} = {(i, 1), (i, 2), (i, 3)}$ . Make each $A_{i}$ independent, put all edges between $A_{1}, A_{2}$ and between $A_{2}, A_{3}$ , and no edges between $A_{1}, A_{3}$ . This blowup has 27 good copies, 9 good copies extending any prescribed middle vertex, and 126 total labelled induced embeddings of $P_{3}$ .

Facts & Assumptions

Given: The three explicit blocks and edges specified in the example, with $P_{3}$ labelled $1, 2, 3$ .

[F1]

From Labelled blowup and good induced copy: For $I \subseteq V (J)$ , a good embedding of $J [I]$ is an induced embedding $ϕ$ satisfying $ϕ (i) \in A_{i}$ for every $i \in I$ .

[F2]

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

[F3]

From The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ : $∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣$

Verification

1.1

The prescribed pairs have zero wrong adjacencies in either direction, so the displayed sets form a $(3, 0)$ -blowup and also a $(3, 1 / 3)$ -blowup. By [F1], each choice of one vertex from its assigned block gives a good embedding; conversely such an embedding has exactly those three choices. Thus [F3] counts $3 \cdot 3 \cdot 3 = 27$ .

F1F3

2.1

If the middle image is fixed, the endpoint choices are independently the three vertices of $A_{1}$ and of $A_{3}$ , giving $3 \cdot 3 = 9$ by [F3]. The lower bound [F2] at $t = j = 3$ , $∣ I ∣ = 1$ , is $(3 / 3)^{2} = 1$ , so this instance exceeds that bound. For the empty partial embedding it is $(3 / 3)^{3} = 1$ , also below the exact 27.

F2F3step 1.1

3.1

The full host is $K_{3, 6}$ with parts $A_{2}$ and $A_{1} \cup A_{3}$ . An induced $P_{3}$ has its center in one part and two distinct ordered endpoints in the other. Centers in $A_{2}$ give $3 \cdot 6 \cdot 5 = 90$ embeddings; centers in the other part give $6 \cdot 3 \cdot 2 = 36$ . Both counts follow by successive choices, and the two cases partition all embeddings. The total is $90 + 36 = 126$ , including choices whose endpoints lie in the same original block.

step 1.1step 2.1algebra∎

Source notes

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

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09Open item page →

Checking the subreciprocal condition for the quadratic log bound

Example

For $ℓ (x) = 2$ on $(0, 1 / 2)$ , the subreciprocal inequalities are $1 < 2 < 1 / x$ and $\log_{2} ℓ (x) = 1$ . At $x = 1 / 16$ the classical density fraction with symbolic constant $C > 0$ is $2^{- 16 C}$ .

Facts & Assumptions

Given: $ℓ (x) = 2$ , $0 < x < 1 / 2$ , and $C > 0$ symbolic.

[F1]

From Subreciprocal function and ell divisibility: A function $ℓ : (0, 1 / 2) \to (0, \infty)$ is subreciprocal when it is nonincreasing and satisfies $1 < ℓ (x) \leq 1 / x$ throughout its domain.

[F2]

From Fox sudakov quantitative induced density bound: $δ = 2^{- C_{H} (\log_{2} (1 / x))^{2}}$

Verification

1.1

The constant function is positive and nonincreasing. For $0 < x < 1 / 2$ , reciprocation gives $1 / x > 2 > 1$ , so it meets [F1]. Also $2^{1} = 2$ , hence $\log_{2} ℓ (x) = 1$ .

F1given

2.1

The value $1 / 16$ lies in that interval, and $\log_{2} (1 / (1 / 16)) = \log_{2} 16 = 4$ . Substitution into [F2] with $C_{H} = C$ yields exponent $C \cdot 4^{2} = 16 C$ and fraction $2^{- 16 C}$ . Here $C$ is a symbolic admissible constant, not a numerically certified constant for arbitrary $H$ .

F2step 1.1algebra∎

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, Section 5, ell=2.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09Open item page →

Checking the subreciprocal condition for the loglog bound

Example

For $ℓ (x) = \log_{2} (1 / x)$ on $(0, 1 / 2)$ , the function is subreciprocal. At $x = 1 / 16$ we have $ℓ (x) = 4$ and $\log_{2} ℓ (x) = 2$ , and the loglog density fraction with symbolic constant $C > 0$ is $2^{- 8 C}$ .

Facts & Assumptions

Given: $ℓ (x) = \log_{2} (1 / x)$ , $0 < x < 1 / 2$ , and $C > 0$ symbolic.

[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]

From Loglog quantitative induced density bound: $δ = 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)}$ .

Verification

1.1

For $0 < x < 1 / 2$ , reciprocation and the increasing logarithm show $ℓ (x) > 1$ and make $ℓ$ nonincreasing. The bound $\log_{2} y \leq y$ at $y = 1 / x > 2$ implicit in the subreciprocity assertion [F1] gives $ℓ (x) \leq 1 / x$ . Thus all subreciprocal conditions hold, including positivity of $\log_{2} ℓ (x)$ .

F1given

2.1

At $x = 1 / 16$ , $1 / x = 16 = 2^{4}$ , so $ℓ (x) = 4 = 2^{2}$ and $\log_{2} ℓ (x) = 2$ . Substituting in [F2] with $C_{H} = C$ gives exponent $C \cdot 4^{2} / 2 = 8 C$ and fraction $2^{- 8 C}$ . The parameter $C$ remains symbolic.

F2step 1.1algebra∎

Source notes

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

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09Open item page →

Comparing the two quantitative density scales

Example

Fix $C_{1}, C_{2} > 0$ . For $0 < x < 1 / 2$ put $L = \log_{2} (1 / x)$ , $D_{1} = 2^{- C_{1} L^{2}}$ and $D_{2} = 2^{- C_{2} L^{2} / \log_{2} L}$ . The ratio of logarithmic losses is $\frac{\log_{2} (1 / D_{2})}{\log_{2} (1 / D_{1})} = \frac{C_{2}}{C_{1} \log_{2} L},$ and tends to zero as $x$ decreases to zero. Consequently $D_{2} > D_{1}$ for all sufficiently small $x$ . With $C_{1} = C_{2} = C$ and $x = 1 / 16$ , the fractions are $D_{1} = 2^{- 16 C}$ and $D_{2} = 2^{- 8 C}$ .

Facts & Assumptions

Given: $C_{1}, C_{2} > 0$ , $0 < x < 1 / 2$ , and $L, D_{1}, D_{2}$ as defined in the example.

[F1]

From Fox sudakov quantitative induced density bound: $δ = 2^{- C_{H} (\log_{2} (1 / x))^{2}}$

[F2]

From Loglog quantitative induced density bound: $δ = 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)}$ .

[F3]

$\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).

Verification

1.1

The two fractions have the forms in [F1] and [F2], with their constants allowed to differ. Since $L > 1$ , both losses are positive. Applying [F3] to their reciprocals yields losses $C_{1} L^{2}$ and $C_{2} L^{2} / \log_{2} L$ . Dividing and cancelling $L^{2} > 0$ gives $C_{2} / (C_{1} \log_{2} L)$ .

F1F2F3

2.1

For any $r > 0$ , take $x_{r} = 2^{- 2^{C_{2} / (C_{1} r) + 1}} \in (0, 1 / 2)$ . If $0 < x < x_{r}$ , then $L > 2^{C_{2} / (C_{1} r) + 1}$ and $\log_{2} L > C_{2} / (C_{1} r) + 1$ , so the ratio is less than $r$ . This proves the stated zero limit. Taking $r = 1$ makes the second loss smaller than the first; strict increase of base-two exponentiation gives $D_{2} > D_{1}$ after negating the losses.

step 1.1algebra

3.1

At $x = 1 / 16$ one has $L = 4$ and $\log_{2} L = 2$ . For equal constants $C > 0$ , the losses are $16 C$ and $8 C$ , so $D_{1} = 2^{- 16 C} < 2^{- 8 C} = D_{2}$ . The eventual comparison above does not assert dominance throughout the interval for unrelated constants.

step 1.1step 2.1algebra∎

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 1.7–1.8, numerical comparison.

Sources

Bucic, Nguyen, Scott and Seymour, Induced subgraph density I