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.

Fox–Sudakov: a quantitative density form of Rödl's 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}} ∣ V (G) ∣$ such that one of the induced graphs $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges.

Remarks

This page uses only that $H$ -free specialization and keeps the source's base-2 logarithm convention. A local proof belongs to the quantitative induced-density track rather than to this page, so the result is recorded here and cited by Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\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.5 (standard reference, not scraped)