LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedaudited 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.

Qid logarithmic and constant divisibility

Statement

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)$ . The divisibility constants may depend on $H$ .

Facts & Assumptions

Given: A nonempty finite graph $H$ and the two functions $\log_{2} (1 / x)$ and $2$ on $(0, 1 / 2)$ .

[F1]

For each nonempty $H$ , constants $k_{1}, k_{2} > 0$ make a strict bound ${ind}_{H} (G) < x^{k_{1}} ∣ G ∣^{∣ H ∣}$ yield a QID $x$ -restricted sequence of length at least $2 \log_{2} (1 / x)$ and width at least $⌊ x^{k_{2}} ∣ G ∣ ⌋$ when $G$ is nonempty and $0 < x \leq 1 / (8 ∣ H ∣)$ . At least half its indices form a subsequence uniformly $x$ -sparse in $G$ or in $\overline{G}$ , so that subsequence has length at least $\log_{2} (1 / x)$ and the same width lower bound. (Special copy trichotomy produces a restricted blockade).

[F2]

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. A nonempty finite $H$ is $ℓ$ -divisive if fixed witnesses $0 < c < 1 / 2$ and $d > 1$ ensure that for every $0 < x < c$ and nonempty finite $G$ , the bound ${ind}_{H} (G) \leq x^{d} ∣ G ∣^{∣ H ∣}$ yields a QID sequence uniformly $x$ -sparse in one of $G, \overline{G}$ , with length at least $ℓ (x)$ and width at least $⌊ x^{d} ∣ G ∣ ⌋$ .

[F3]

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

[F4]

For $b > 0$ , $b \neq 1$ , and $x > 0$ , $\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).

[F5]

The natural logarithm $\log : (0, \infty) \to R$ is strictly increasing and $\log 1 = 0$ . (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

1.1F4F5algebra

By [F5], $\log 2 > 0$ , so [F4] implies that $\log_{2}$ is strictly increasing and $\log_{2} 2 = 1$ . Its inverse $u \mapsto 2^{u}$ is also strictly increasing: if $u < v$ but $2^{u} \geq 2^{v}$ , applying $\log_{2}$ would give $u \geq v$ . Likewise, for any fixed $0 < a < 1$ , [F5] gives $\log a < 0$ , so $\log_{a}$ is strictly decreasing by [F4]. If $u < v$ but $a^{u} \leq a^{v}$ , applying $\log_{a}$ would give $u \geq v$ ; thus $a^{u} > a^{v}$ .

2.1F3F4step 1.1algebra

For $y \geq 2$ , let $N = ⌊ \log_{2} y ⌋$ by [F3]. Then $N \geq 1$ and $N \leq \log_{2} y < N + 1$ . The integer inequality $2^{N} \geq N + 1$ follows by induction: it is equality at $N = 1$ , and $2^{N + 1} \geq 2 N + 2 \geq N + 2$ . Thus [F4] and step 1.1 give $\log_{2} y < N + 1 \leq 2^{N} \leq y$ . In particular $\log_{2} y \leq y$ without an asymptotic restriction.

3.1F2step 1.1step 2.1algebra

If $0 < x < 1 / 2$ , then $y = 1 / x > 2$ , so $1 < \log_{2} (1 / x) \leq 1 / x$ by the preceding bound. As $x$ increases, $1 / x$ decreases and the increasing logarithm makes $\log_{2} (1 / x)$ nonincreasing. The constant function 2 is nonincreasing and $1 < 2 < 1 / x$ . Both satisfy [F2].

4.1F1F2F3step 1.1step 3.1

For fixed $H$ choose $k_{1}, k_{2}$ from [F1] and any $d > \max (1, k_{1}, k_{2})$ . Let $c = 1 / (16 ∣ H ∣)$ . For $0 < x < c$ and nonempty $G$ , the premise ${ind}_{H} (G) \leq x^{d} ∣ G ∣^{∣ H ∣}$ implies ${ind}_{H} (G) < x^{k_{1}} ∣ G ∣^{∣ H ∣}$ because $0 < x < 1$ and $d > k_{1}$ . The uniformly $x$ -sparse subsequence supplied by [F1] has length at least $\log_{2} (1 / x)$ and width at least $⌊ x^{k_{2}} ∣ G ∣ ⌋ \geq ⌊ x^{d} ∣ G ∣ ⌋$ by floor monotonicity: if $u \leq v$ but $⌊ u ⌋ > ⌊ v ⌋$ , integrality and [F3] give $u \geq ⌊ u ⌋ \geq ⌊ v ⌋ + 1 > v$ , a contradiction. These are the required witnesses for logarithmic divisibility.

5.1F2step 1.1step 4.1algebra∎

The same witnesses have $c \leq 1 / 16 < 1 / 4$ , hence $x < c$ gives $\log_{2} (1 / x) > 2$ . The same uniformly $x$ -sparse subsequence therefore has length at least 2 and the same width. This witnesses constant divisibility, including every zero-floor-width case.

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 5.1 and paragraph on constant ell before it.

Depends on

Used by

Fox sudakov quantitative induced density bound Corollary
Checking the subreciprocal condition for the loglog bound Example
Loglog quantitative induced density bound Theorem

Dependency tree · two levels

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