RemarkRemark: AI-adaptedProof: Not suppliedSession-authored (Fable 5 assisted)‡ sources checked 2026-08-26‡ not proved here

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.

‡ Recorded, not proved here. This statement is included so the library can refer to it honestly, with a citation to the literature. It is not proved anywhere in this library: the track that would prove it has not been developed here yet.

Bucić–Nguyen–Scott–Seymour: a log-log quantitative density theorem

Statement

For every finite graph $H$ there exists a constant $C_{H} > 0$ such that for every real $x$ with $0 < x < 1 / 2$ and every finite $H$ -free graph $G$ , there is a vertex set $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)} ∣ V (G) ∣$ such that one of the induced graphs $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges.

Remarks

Again the statement is recorded exactly in the paper's base-2 convention. The page uses it only as a source-cited input for Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n \log_{2} \log_{2} n}}$ .

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Matija Bucić, Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. I. A loglog step towards Erdős-Hajnal, Theorem 1.8 (standard reference, not scraped)