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.

Ell divisibility amplifies through a blockade

Statement

Let $ℓ$ be subreciprocal and let the nonempty finite graph $H$ be $ℓ$ -divisive with witnesses $0 < c < 1 / 2$ , $d > 1$ . Write $h = ∣ H ∣$ . Put $z = ℓ (c)^{- 1 / 2}$ , $b = 2 - \log_{2} (1 - z)$ , and for $0 < ϵ < c$ put $x = 2^{1 - b} ϵ$ , $p = z ℓ (x)$ , $η = x^{d} / 4$ , $t = - ⌊ - 2 \log_{2} (1 / ϵ) / \log_{2} p ⌋$ and $δ = 2^{- 20 b d \log_{2} (1 / ϵ)^{2} / \log_{2} ℓ (ϵ)}$ . Fix a nonempty finite $G$ with $n = ∣ G ∣$ , ${ind}_{H} (G) \leq (δ n)^{h}$ and $δ n > 1$ . Let $β_{r}$ be its finite density profile with parameter $η$ . For $1 \leq s \leq t$ and $u, v \geq ϵ$ , $β_{s - 1} (u, v) \geq η \min {β_{s} (p u, v), β_{s} (u, p v)} .$

Facts & Assumptions

Given: All parameters and the fixed host $G$ as in the statement, including $δ ∣ G ∣ > 1$ , the non-strict copy bound, $1 \leq s \leq t$ , and $u, v \geq ϵ$ .

[F1]

For the stated $ℓ, c, d, ϵ$ , the parameters satisfy $0 < x < ϵ < c$ , $0 < η < 1$ , $p > 1$ , $p^{2} \geq ℓ (x)$ , and $δ < x^{d} η^{t}$ ; $t$ is the least natural with $p^{t} \geq ϵ^{- 2}$ . (Admissible parameters for the density recursion).

[F2]

From Subreciprocal function and ell divisibility: A nonempty finite graph $H$ is $ℓ$ -divisive if there are witnesses $0 < c < 1 / 2$ and $d > 1$ such that for every $0 < x < c$ and every nonempty finite graph $G$ , the inequality ${ind}_{H} (G) \leq x^{d} ∣ G ∣^{∣ H ∣}$ implies a QID block sequence of length at least $ℓ (x)$ , width at least $⌊ x^{d} ∣ G ∣ ⌋$ , uniformly $x$ -sparse in one of $G, \overline{G}$ .

[F3]

From Qid finite density recursion profile: Every qualifying induced $F$ therefore has a nonempty $T$ with $∣ T ∣ \geq β_{s} (a, b) ∣ F ∣$ and $e (F [T]) \leq a (\binom{∣ T ∣}{2})$ or $e (\overline{F} [T]) \leq b (\binom{∣ T ∣}{2})$ : choose a maximizing set for $ρ_{F}$ .

[F4]

From Qid bipartite density trimming: If $e_{G} (A, B) \leq c ∣ A ∣ ∣ B ∣$ , then some $A^{'} \subseteq A$ with $∣ A^{'} ∣ \geq ∣ A ∣ / 2$ has $∣ N_{G} (v) \cap B ∣ \leq 2 c ∣ B ∣$ for every $v \in A^{'}$ .

[F5]

From Qid fixed size density selection: Independently, if $2 \leq m \leq N$ , some $m$ -subset $C \subseteq A$ satisfies $e (G [C]) / (\binom{m}{2}) \leq e (G [A]) / (\binom{N}{2})$ . For $m = 1$ the internal edge count is zero.

[F6]

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

[F7]

For every natural $n$ , $(\binom{n}{2}) = n (n - 1) / 2$ when the natural numbers are viewed in the real field. (A finite set with $n$ elements has exactly $(\binom{n}{2})$ two-element subsets, and $2 (\binom{n}{2}) = n (n - 1)$ ).

Proof

1.1F1given

Set $γ_{1} = β_{s} (p u, v)$ , $γ_{2} = β_{s} (u, p v)$ and $γ = \min (γ_{1}, γ_{2}) > 0$ . Take any induced $F$ with $N = ∣ F ∣ \geq η^{s - 1} n$ . From [F1] and $δ n > 1$ we have $n > δ^{- 1} > η^{- t}$ , so $N > η^{s - 1 - t} \geq η^{- 1}$ . Embeddings in $F$ inject into those in $G$ by inclusion. Hence ${ind}_{H} (F) \leq (δ n)^{h} \leq (δ η^{- (s - 1)} N)^{h} \leq (x^{d} N)^{h} \leq x^{d} N^{h}$ , using $δ < x^{d} η^{t}$ , $s \leq t$ , $h \geq 1$ , and $0 < x < 1$ .

2.1F2F6step 1.1

Now $0 < x < c$ , so [F2] gives a uniform sequence $(B_{1}, \dots, B_{k})$ in $F$ or $\overline{F}$ with $k \geq ℓ (x)$ and $∣ B_{i} ∣ \geq ⌊ x^{d} N ⌋ = ⌊ 4 η N ⌋ \geq 2 η N$ . For the last bound, [F6] gives $⌊ 4 η N ⌋ > 4 η N - 1 \geq 2 η N$ since $η N > 1$ . All blocks are therefore nonempty.

3.1F4F6step 2.1

First suppose the sequence is $x$ -sparse in $F$ . Set $m = - ⌊ - η γ_{1} N ⌋$ . By [F6], $η γ_{1} N \leq m < η γ_{1} N + 1$ and $m \geq 1$ . Process blocks from $k$ down to $1$ . At step $i$ , let $D_{i}$ be the union of the already selected, pairwise disjoint $m$ -sets $C_{j}$ with $j > i$ . Because $D_{i}$ is $x$ -sparse to $B_{i}$ , $e_{F} (B_{i}, D_{i}) \leq x ∣ B_{i} ∣ ∣ D_{i} ∣$ . Applying [F4] in the direction from $B_{i}$ to $D_{i}$ gives $B_{i}^{'} \subseteq B_{i}$ with $∣ B_{i}^{'} ∣ \geq ∣ B_{i} ∣ / 2 \geq η N \geq η^{s} n$ and degrees into $D_{i}$ at most $2 x ∣ D_{i} ∣$ . If the tail is empty, take $B_{i}^{'} = B_{i}$ , so the construction starts.

4.1F3F5step 3.1

Apply [F3] inside $F [B_{i}^{'}]$ with thresholds $(p u, v)$ . It yields a nonempty $E_{i}$ of size at least $γ_{1} ∣ B_{i}^{'} ∣ \geq η γ_{1} N$ . If $e (\overline{F} [E_{i}]) \leq v (\binom{∣ E_{i} ∣}{2})$ , take $T = E_{i}$ : its size is already at least $η γ N$ . Otherwise $e (F [E_{i}]) \leq p u (\binom{∣ E_{i} ∣}{2})$ . The integer $∣ E_{i} ∣$ is at least the least integer $m$ above $η γ_{1} N$ , so [F5] gives an exact $m$ -subset $C_{i}$ with $e (F [C_{i}]) \leq p u (\binom{m}{2})$ . For $m = 1$ use its zero edge count. As $C_{i} \subseteq B_{i}^{'}$ , the degree bound into the already fixed tail is preserved.

5.1step 2.1step 4.1algebra

If the construction finishes without a complementary-density set, put $T = ⋃_{i} C_{i}$ . Then $∣ T ∣ = k m \geq η γ N$ . The internal edges total at most $k p u (\binom{m}{2})$ . Each edge between blocks has a unique earlier endpoint block; summing $e (C_{i}, D_{i}) \leq 2 x m^{2} (k - i)$ gives at most $2 x m^{2} (\binom{k}{2})$ cross edges. Since $p / k \leq z$ and $2 x = (1 - z) ϵ \leq (1 - z) u$ , the total is at most $u [z k^{2} (\binom{m}{2}) + (1 - z) m^{2} (\binom{k}{2})]$ .

6.1F7step 5.1algebra

By [F7], $(\binom{k m}{2}) - k^{2} (\binom{m}{2}) = k m (k - 1) / 2 \geq 0$ and $(\binom{k m}{2}) - m^{2} (\binom{k}{2}) = k m (m - 1) / 2 \geq 0$ . Taking their convex combination with weights $z, 1 - z$ proves $e (F [T]) \leq u (\binom{∣ T ∣}{2})$ . These identities are valid at $m = 1$ too, so no density quotient by zero was used.

7.1F3F5F6step 2.1step 3.1step 6.1

If the sequence supplied in step 2.1 is sparse in $\overline{F}$ , run the same selection with degrees counted in $\overline{F}$ , using $γ_{2}$ and $m = - ⌊ - η γ_{2} N ⌋$ . Apply [F3] with the original thresholds $(u, p v)$ in each $F [B_{i}^{'}]$ . A low-density set in $F$ finishes immediately; otherwise the chosen set has complementary edge bound $p v$ , to which [F5] in $\overline{F}$ applies. The calculation of steps 5.1 and 6.1, with $v$ replacing $u$ , bounds complementary edges by $v (\binom{∣ T ∣}{2})$ . This uses the already obtained sequence; it never assumes $\overline{F}$ is $H$ -free or satisfies an $H$ -copy bound.

8.1F3step 4.1step 6.1step 7.1∎

Thus every induced $F$ at cutoff $η^{s - 1} n$ has a nonempty qualifying $T$ of relative size at least $η γ$ . Taking the minimum of $ρ_{F} (u, v)$ over that family, as in [F3], gives $β_{s - 1} (u, v) \geq η γ$ , the asserted recurrence.

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 5.2 claim (1).

Depends on

Used by

Quantitative density theorem for ell divisive graphs Theorem

Dependency tree · two levels

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