Session-authored (Fable 5 assisted)

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.

✓ 19 results · all verified · 8 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 11 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Regular Pairs and Induced Counting

1 · Prerequisites

2 · Summary

A finite simple graph and its complement, the edges between two vertex sets and the pure and mixed pairs among them, an induced embedding, an induced copy of a fixed graph, the number of such copies, and what it means for a class of graphs to be hereditary are all published notions. From finite probability the development takes the Cauchy–Schwarz inequality for finite random variables, Markov's inequality, and the first-moment method; these are the inequalities behind the energy increment and behind every statement that all but a small fraction of vertices or pairs behave typically.

The page defines the edge density between two vertex sets and the $ϵ$ -regular pair, then makes that definition usable through typical degrees, slicing, complementation, and robustness under small edits. Regular and equitable partitions and the mean-square density, or energy, of a partition follow: energy is monotone under refinement, an irregularity witness forces a quantified energy boost, and iterating the increment proves the Szemerédi regularity lemma with an equitable partition, an explicit tower-type upper bound, and a refinement of any prescribed partition. Regular pairs then support triangle counting, counting copies of a fixed graph, and induced counting, which with edit distance give the graph removal lemma. Strong regularity by energy stabilisation, large self-regular subsets, the density-approximation lemma, and representative subsets carry the argument to the induced removal lemma, with a remark separating the tower and wowzer bounds.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Edge counts and densities between nonempty vertex sets

Definition

Let $G$ be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets) and let $X, Y \subseteq V (G)$ . Define the ordered cross-edge count $e_{G} (X, Y) : = ∣ {(x, y) \in X \times Y : x y \in E (G)} ∣ .$ When $X$ and $Y$ are nonempty, their edge density is $d_{G} (X, Y) : = \frac{e_{G} (X, Y)}{∣ X ∣ ∣ Y ∣} .$ We omit the subscript when the graph is clear. If $X$ and $Y$ are disjoint, this agrees with the edges between sets in Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs. If they overlap, an edge with both endpoints in $X \cap Y$ contributes in both orientations, while diagonal pairs $(x, x)$ never contribute.

For a nonempty graph, write $d (G) : = d_{G} (V (G), V (G)) = 2 ∣ E (G) ∣ / ∣ V (G) ∣^{2}$ . By convention the density of the null graph is $0$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

$ϵ$ -regular pairs and self-regular vertex sets

Definition

Let $X, Y$ be nonempty vertex sets in a graph and let $ϵ > 0$ . The pair $(X, Y)$ is $ϵ$ -regular if every $A \subseteq X$ and $B \subseteq Y$ with $∣ A ∣ \geq ϵ ∣ X ∣$ and $∣ B ∣ \geq ϵ ∣ Y ∣$ satisfies $∣ d (A, B) - d (X, Y) ∣ \leq ϵ .$ If this fails, such $A, B$ are an irregularity witness. The definition permits $X = Y$ and permits overlap. A nonempty vertex set $X$ is $ϵ$ -self-regular when $(X, X)$ is $ϵ$ -regular (Edge counts and densities between nonempty vertex sets).

We also call a pair $0$ -regular when every pair of nonempty subsets $A \subseteq X$ , $B \subseteq Y$ has $d (A, B) = d (X, Y)$ . This is the exact limiting form of the positive-parameter definition and avoids assigning a density to an empty subpair.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-16Open item page →

Complementation sends a disjoint $ϵ$ -regular pair of density $d$ to one of density $1 - d$

Statement

Let $X, Y$ be disjoint nonempty vertex sets. If $(X, Y)$ is $ϵ$ -regular of density $d$ in $G$ , then it is $ϵ$ -regular of density $1 - d$ in $\overline{G}$ .

Facts & Assumptions

Given: Disjoint nonempty sets $X, Y$ forming an $ϵ$ -regular pair of density $d$ in $G$ .

[L1]

Regularity means that every sufficiently large subpair $(A, B)$ has density within $ϵ$ of $d (X, Y)$ ( $ϵ$ -regular pairs and self-regular vertex sets).

[L2]

In the complement, exactly the missing pairs of distinct vertices are edges (Graph isomorphisms, automorphisms and graph complements).

Proof

technique · direct

1.1

Because $X$ and $Y$ are disjoint, every ordered pair in $A \times B$ consists of distinct vertices and is an edge in exactly one of $G, \overline{G}$ ; hence $d_{\overline{G}} (A, B) = 1 - d_{G} (A, B)$ for every nonempty $A \subseteq X$ , $B \subseteq Y$ .

givenL2

2.1

Taking $A = X, B = Y$ gives $d_{\overline{G}} (X, Y) = 1 - d$ .

step 1.1

3.1

For every subpair meeting the thresholds in [L1], $∣ d_{\overline{G}} (A, B) - (1 - d) ∣ = ∣ d_{G} (A, B) - d ∣ \leq ϵ$ , so the complemented pair is $ϵ$ -regular.

step 1.1step 2.1L1∎

Disjointness is essential for the exact density formula. When $X$ and $Y$ overlap, diagonal pairs are edges in neither graph and contribute a correction of $∣ X \cap Y ∣ / (∣ X ∣ ∣ Y ∣)$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

In a regular pair, fewer than $ϵ ∣ X ∣$ vertices have too small a degree into a large subset, and fewer than $ϵ ∣ X ∣$ have too large a degree

Statement

Suppose $(X, Y)$ is an $ϵ$ -regular pair of density $d$ , and $Y^{'} \subseteq Y$ satisfies $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ . Then fewer than $ϵ ∣ X ∣$ vertices $x \in X$ have $∣ N (x) \cap Y^{'} ∣ < (d - ϵ) ∣ Y^{'} ∣,$ and fewer than $ϵ ∣ X ∣$ vertices have $∣ N (x) \cap Y^{'} ∣ > (d + ϵ) ∣ Y^{'} ∣ .$

Facts & Assumptions

Given: An $ϵ$ -regular pair $(X, Y)$ of density $d$ and a set $Y^{'} \subseteq Y$ with $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ .

[L1]

Every $A \subseteq X$ , $B \subseteq Y$ with $∣ A ∣ \geq ϵ ∣ X ∣$ and $∣ B ∣ \geq ϵ ∣ Y ∣$ satisfies $∣ d (A, B) - d (X, Y) ∣ \leq ϵ$ ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · contradiction

1.1

Let $A$ be the set of all $x \in X$ with $∣ N (x) \cap Y^{'} ∣ < (d - ϵ) ∣ Y^{'} ∣$ and let $B$ be the set of all $x \in X$ with $∣ N (x) \cap Y^{'} ∣ > (d + ϵ) ∣ Y^{'} ∣$ . Suppose, for contradiction, that $∣ A ∣ \geq ϵ ∣ X ∣$ .

assume-contragivenchoose

2.1

Summing degrees over $A$ gives $e (A, Y^{'}) < (d - ϵ) ∣ A ∣ ∣ Y^{'} ∣$ , hence $d (A, Y^{'}) < d - ϵ$ . Since $∣ A ∣ \geq ϵ ∣ X ∣$ and $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ , this contradicts [L1]. Therefore $∣ A ∣ < ϵ ∣ X ∣$ .

step 1.1L1algebra

3.1

Assume likewise that $∣ B ∣ \geq ϵ ∣ X ∣$ . Summing degrees over $B$ gives $d (B, Y^{'}) > d + ϵ$ , and the same two size conditions again contradict [L1]. Therefore $∣ B ∣ < ϵ ∣ X ∣$ .

step 2.1L1algebra

4.1

Both exceptional sets therefore have size strictly below $ϵ ∣ X ∣$ , which is the Statement.

step 2.1step 3.1discharge-contradiction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Slicing lemma: large subpairs remain regular and their density shifts by at most $ϵ$

Statement

Let $(X, Y)$ be $ϵ$ -regular, and let $X^{'} \subseteq X$ , $Y^{'} \subseteq Y$ satisfy $∣ X^{'} ∣ \geq α ∣ X ∣$ and $∣ Y^{'} ∣ \geq β ∣ Y ∣$ , where $α, β \geq ϵ > 0$ . Then $∣ d (X^{'}, Y^{'}) - d (X, Y) ∣ \leq ϵ,$ and $(X^{'}, Y^{'})$ is $ϵ^{'}$ -regular for $ϵ^{'} = \max {ϵ / α, ϵ / β, 2 ϵ} .$

Facts & Assumptions

Given: The pair and subsets in the Statement.

[L1]

An $ϵ$ -regular pair has every subpair whose two sides meet the $ϵ$ relative-size thresholds within $ϵ$ of its density ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · direct

1.1

Since $∣ X^{'} ∣ \geq ϵ ∣ X ∣$ and $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ , [L1] gives $∣ d (X^{'}, Y^{'}) - d (X, Y) ∣ \leq ϵ$ .

givenL1

1.2

Let $A \subseteq X^{'}$ and $B \subseteq Y^{'}$ satisfy $∣ A ∣ \geq ϵ^{'} ∣ X^{'} ∣$ and $∣ B ∣ \geq ϵ^{'} ∣ Y^{'} ∣$ . Then $∣ A ∣ \geq (ϵ / α) α ∣ X ∣ = ϵ ∣ X ∣$ and similarly $∣ B ∣ \geq ϵ ∣ Y ∣$ .

givenalgebra

2.1

By [L1], $∣ d (A, B) - d (X, Y) ∣ \leq ϵ$ ; combining this with step 1.1 yields $∣ d (A, B) - d (X^{'}, Y^{'}) ∣ \leq 2 ϵ \leq ϵ^{'}$ .

step 1.1step 1.2L1algebra

3.1

Since $A, B$ were arbitrary at the $ϵ^{'}$ thresholds, $(X^{'}, Y^{'})$ is $ϵ^{'}$ -regular.

step 2.1L1∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Regularity survives sufficiently small changes of vertices and cross-edges

Statement

Let $0 < ϵ < ϵ^{'} \leq 1$ . There is $δ > 0$ with the following property. If $(X, Y)$ is $ϵ$ -regular, $X^{'}, Y^{'}$ are obtained by adding or deleting at most $δ ∣ X ∣$ and $δ ∣ Y ∣$ vertices respectively, and at most $δ ∣ X ∣ ∣ Y ∣$ cross-edge incidences are changed, then $(X^{'}, Y^{'})$ is $ϵ^{'}$ -regular.

Facts & Assumptions

Given: Parameters and an edited pair as in the Statement.

[L1]

In an $ϵ$ -regular pair, every subpair meeting the $ϵ$ relative-size thresholds has density within $ϵ$ of the original density ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · contradiction

1.1

Choose $δ > 0$ so small that $2 δ < ϵ^{'} - ϵ$ , $δ < 1 / 2$ , and $20 δ / ϵ^{2} < ϵ^{'} - ϵ$ .

givenchoose

2.1

Suppose, for contradiction, that $A^{'} \subseteq X^{'}$ and $B^{'} \subseteq Y^{'}$ witness failure of $ϵ^{'}$ -regularity. Put $A = A^{'} \cap X$ and $B = B^{'} \cap Y$ . The vertex-change bounds and step 1.1 give $∣ A ∣ \geq ϵ ∣ X ∣$ and $∣ B ∣ \geq ϵ ∣ Y ∣$ .

assume-contrastep 1.1algebra

3.1

Removing the added vertices and accounting for the changed incidences changes either the witness density or the full-pair density by at most $10 δ / ϵ^{2}$ ; this follows by dividing at most the affected rows, columns, and $δ ∣ X ∣ ∣ Y ∣$ changed incidences by the lower bounds $∣ A^{'} ∣ ∣ B^{'} ∣ \geq ϵ^{2} (1 - δ)^{2} ∣ X ∣ ∣ Y ∣$ .

step 1.1step 2.1algebra

4.1

Hence $∣ d (A, B) - d (X, Y) ∣ > ϵ^{'} - 20 δ / ϵ^{2} > ϵ$ , contradicting [L1].

step 3.1L1algebra

5.1

The contradiction proves that every sufficiently small edit, in particular the chosen $δ$ , leaves the pair $ϵ^{'}$ -regular.

step 4.1discharge-contradiction∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

$ϵ$ -regular vertex partitions, equitable partitions, and refinement

Definition

Let $G$ be a nonempty graph and let $P = {V_{1}, \dots, V_{k}}$ be a partition of $V (G)$ into nonempty parts. For $ϵ > 0$ , the partition is $ϵ$ -regular if $\sum_{(i, j) : (V_{i}, V_{j}) is not ϵ -regular} ∣ V_{i} ∣ ∣ V_{j} ∣ \leq ϵ ∣ V (G) ∣^{2},$ where ordered pairs and the diagonal pairs $i = j$ are included ( $ϵ$ -regular pairs and self-regular vertex sets).

The partition is equitable if $∣ ∣ V_{i} ∣ - ∣ V_{j} ∣ ∣ \leq 1$ for all $i, j$ . A partition $Q$ refines $P$ if every part of $Q$ is contained in a part of $P$ . The empty family is the unique partition of the null graph and is equitable and $ϵ$ -regular by convention.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The mean-square density, or energy, of a vertex partition

Definition

Let $G$ have order $n > 0$ . For vertex sets $X, Y$ and partitions $A$ of $X$ , $B$ of $Y$ into nonempty sets, define their pair energy by $q (A, B) : = \frac{1}{n^{2}} \sum_{A \in A} \sum_{B \in B} ∣ A ∣ ∣ B ∣ d (A, B)^{2} .$ For a vertex partition $P$ of $G$ ( $ϵ$ -regular vertex partitions, equitable partitions, and refinement), its energy, or mean-square density, is $q (P) : = q (P, P) = \frac{1}{n^{2}} \sum_{A, B \in P} ∣ A ∣ ∣ B ∣ d (A, B)^{2},$ using the ordered-pair density of Edge counts and densities between nonempty vertex sets. The empty partition of the null graph has energy $0$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

An irregularity witness raises the pair energy by more than $ϵ^{4} ∣ X ∣ ∣ Y ∣ / n^{2}$

Statement

Let $G$ have order $n > 0$ , let $X, Y \subseteq V (G)$ be nonempty, and suppose that $A \subseteq X$ , $B \subseteq Y$ witness that $(X, Y)$ is not $ϵ$ -regular. If $A = {A, X ∖ A}$ and $B = {B, Y ∖ B}$ after empty cells are omitted, then $q (A, B) - \frac{∣ X ∣ ∣ Y ∣}{n^{2}} d (X, Y)^{2} > ϵ^{4} \frac{∣ X ∣ ∣ Y ∣}{n^{2}} .$

Facts & Assumptions

Given: An irregular pair and witness sets as in the Statement.

[L1]

Such witnesses satisfy $∣ A ∣ \geq ϵ ∣ X ∣$ , $∣ B ∣ \geq ϵ ∣ Y ∣$ , and $∣ d (A, B) - d (X, Y) ∣ > ϵ$ ( $ϵ$ -regular pairs and self-regular vertex sets).

[L2]

Pair energy is the product-size-weighted mean square of the densities of the refined subpairs (The mean-square density, or energy, of a vertex partition).

Proof

technique · direct

1.1

Choose $(x, y)$ uniformly from $X \times Y$ , and let $Z$ be the density between the cells of $A$ and $B$ containing $x$ and $y$ . Double-counting gives $E Z = d (X, Y)$ , and [L2] identifies $∣ X ∣ ∣ Y ∣ E (Z^{2}) / n^{2}$ with $q (A, B)$ .

givenL2algebra

2.1

Therefore the energy gain in the Statement is $(∣ X ∣ ∣ Y ∣ / n^{2}) Var (Z) = (∣ X ∣ ∣ Y ∣ / n^{2}) E ((Z - d (X, Y))^{2})$ .

step 1.1algebra

2.2

On the event $(x, y) \in A \times B$ , which has probability $∣ A ∣ ∣ B ∣ / (∣ X ∣ ∣ Y ∣) \geq ϵ^{2}$ by [L1], the random variable equals $d (A, B)$ and differs from its mean by more than $ϵ$ .

L1step 1.1

3.1

Restricting the nonnegative expectation in step 2.1 to this event gives a strict lower bound $ϵ^{2} ϵ^{2} ∣ X ∣ ∣ Y ∣ / n^{2}$ , which is the asserted boost.

step 2.1step 2.2algebra∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Every nonregular $k$ -part partition has a refinement with energy gain greater than $ϵ^{5}$ and at most $k 2^{k + 1}$ parts

Statement

Let $0 < ϵ < 1$ . If a partition $P$ of a nonempty graph is not $ϵ$ -regular and has $k$ nonempty parts, then it has a refinement $Q$ with at most $k 2^{k + 1}$ parts and $q (Q) > q (P) + ϵ^{5} .$

Facts & Assumptions

Given: A non- $ϵ$ -regular $k$ -part partition $P$ .

[L1]

Nonregularity means that the ordered irregular pairs $(X, Y) \in P^{2}$ have total weight $\sum ∣ X ∣ ∣ Y ∣ > ϵ n^{2}$ ( $ϵ$ -regular vertex partitions, equitable partitions, and refinement).

[L2]

Splitting an irregular pair by witness sets raises its contribution to energy by more than $ϵ^{4} ∣ X ∣ ∣ Y ∣ / n^{2}$ (An irregularity witness raises the pair energy by more than $ϵ^{4} ∣ X ∣ ∣ Y ∣ / n^{2}$ ).

[L3]

Further refinement cannot reduce energy (Energy lies in $[0, 1]$ and cannot decrease under refinement).

Proof

technique · direct

1.1

For each ordered irregular pair $(X, Y)$ choose witness sets $A_{X Y} \subseteq X$ and $B_{X Y} \subseteq Y$ .

givenL1choose

2.1

For each $X \in P$ , refine $X$ by all witness subsets that occur in $X$ , whether as a first or a second coordinate. There are at most $2 k$ such subsets, and the common refinement they generate has at most $2^{2 k}$ cells. By choosing one witness orientation for each unordered pair and retaining the two diagonal witnesses separately, the same construction uses at most $k + 1$ subsets per part and hence at most $2^{k + 1}$ cells. Thus the resulting partition $Q$ has at most $k 2^{k + 1}$ parts.

step 1.1algebra

3.1

For every selected irregular ordered pair, the restriction of $Q$ to its two old parts refines the witness split. By [L2] and [L3], its contribution gains more than $ϵ^{4} ∣ X ∣ ∣ Y ∣ / n^{2}$ ; all other old-pair contributions are nondecreasing.

step 2.1L2L3

4.1

Although only one orientation of each off-diagonal irregular pair supplied witness sets in step 2.1, that single split refines both old parts, so step 3.1 applies to both ordered pairs $(X, Y)$ and $(Y, X)$ , which carry equal weight $∣ X ∣ ∣ Y ∣ / n^{2}$ and equal regularity status. Summing the gains over all ordered irregular pairs therefore recovers the full normalized irregular weight, and by [L1] the total gain is greater than $ϵ^{4} ϵ = ϵ^{5}$ .

step 3.1L1algebra∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_{0}$

Statement

Let $0 < ϵ < 1$ and let $m_{0} \geq 1$ . Define $m_{r + 1} = m_{r} ⌈ ϵ^{- 5} 2^{m_{r} + 5} ⌉, R = ⌈ 2 ϵ^{- 5} ⌉, M = m_{R} .$ Every graph $G$ of order $n \geq M$ has an equitable $ϵ$ -regular vertex partition into $k$ parts with $m_{0} \leq k \leq M .$ In particular, the displayed recurrence is a tower-type upper bound depending only on $ϵ$ and $m_{0}$ .

Facts & Assumptions

Given: Parameters $ϵ, m_{0}$ and a graph $G$ as in the Statement.

[L1]

A non- $ϵ$ -regular $k$ -part partition has a refinement of at most $k 2^{k + 1}$ parts whose energy gains more than $ϵ^{5}$ (Every nonregular $k$ -part partition has a refinement with energy gain greater than $ϵ^{5}$ and at most $k 2^{k + 1}$ parts).

[L2]

Partition energy lies in $[0, 1]$ and is nondecreasing under refinement (Energy lies in $[0, 1]$ and cannot decrease under refinement).

[L3]

An equitable partition has part sizes differing by at most one, and regularity is measured by the total weight of its irregular ordered pairs ( $ϵ$ -regular vertex partitions, equitable partitions, and refinement).

[L4]

$q (P) = n^{- 2} \sum_{A, B \in P} ∣ A ∣ ∣ B ∣ d (A, B)^{2}$ , a sum over ordered pairs of parts with nonnegative weights $∣ A ∣ ∣ B ∣ / n^{2}$ and densities in $[0, 1]$ (The mean-square density, or energy, of a vertex partition).

Proof

technique · direct

1.1

Each factor $⌈ ϵ^{- 5} 2^{m_{r} + 5} ⌉$ is at least $1$ , so $m_{0} \leq m_{1} \leq \dots \leq m_{R} = M \leq n$ . Choose an equitable partition $P_{0}$ of $V (G)$ into exactly $m_{0}$ nonempty parts, whose sizes are then $⌊ n / m_{0} ⌋$ or $⌈ n / m_{0} ⌉$ ; this is possible because $n \geq M \geq m_{0}$ .

givenL3algebrachoose

1.2

Equitisation. Let $P$ be equitable with $k$ parts, let $R$ refine $P$ with at most $K = k 2^{k + 1}$ parts, put $p = ⌈ ϵ^{- 5} 2^{k + 5} ⌉$ , and suppose $k p \leq n$ . Order $V (G)$ so that each part of $P$ is an interval and each cell of $R$ is an interval inside its part, and cut each part $X$ into $p$ consecutive pieces of sizes $⌊ ∣ X ∣ / p ⌋$ or $⌈ ∣ X ∣ / p ⌉$ . Writing $a = ⌊ n / k ⌋$ and $t = ⌊ a / p ⌋ \geq 1$ , every piece has size $t$ or $t + 1$ , because $∣ X ∣ \in {a, a + 1}$ forces $⌊ ∣ X ∣ / p ⌋ \geq t$ and $⌈ ∣ X ∣ / p ⌉ \leq t + 1$ . So the resulting $P^{'}$ is an equitable refinement of $P$ with exactly $k p$ parts.

givenL3algebraconstruct

2.1

Call a piece dirty when it is not contained in a single cell of $R$ , and let $D$ be the union of the dirty pieces. A piece is dirty exactly when it contains a boundary between two consecutive $R$ -cells of the same part, and each of the at most $K - k$ such boundaries lies in one piece, so there are at most $K$ dirty pieces. Each has size at most $⌈ ∣ X ∣ / p ⌉ \leq 2 ∣ X ∣ / p \leq 4 n / (k p)$ , using $p \leq ∣ X ∣$ and $∣ X ∣ \leq ⌈ n / k ⌉ \leq 2 n / k$ . Hence $∣ D ∣ \leq 4 K n / (k p) = 2^{k + 3} n / p \leq ϵ^{5} n / 4$ .

step 1.2algebra

3.1

Energy loss. Let $S$ be the common refinement of $P^{'}$ and $R$ . It refines $R$ , so $q (S) \geq q (R)$ by [L2]. Every piece outside $D$ lies in one $R$ -cell and is therefore itself a cell of $S$ , so in the sums of [L4] the two energies agree term by term on ordered pairs of such pieces. Every other ordered pair has an entry inside $D$ , and those pairs carry total weight at most $2 ∣ D ∣ n / n^{2} = 2 ∣ D ∣ / n$ ; since each squared density lies in $[0, 1]$ , their contribution to each of $q (S)$ and $q (P^{'})$ lies in $[0, 2 ∣ D ∣ / n]$ . Hence $q (P^{'}) \geq q (S) - 2 ∣ D ∣ / n \geq q (R) - ϵ^{5} / 2$ .

step 2.1L2L4algebra

4.1

One round. Suppose $P_{r}$ is equitable, refines $P_{0}$ , has $k_{r}$ parts with $m_{0} \leq k_{r} \leq m_{r}$ , and is not $ϵ$ -regular. Apply [L1] to obtain a refinement $R_{r}$ with at most $k_{r} 2^{k_{r} + 1}$ parts and $q (R_{r}) > q (P_{r}) + ϵ^{5}$ , and let $P_{r + 1}$ be the partition step 1.2 builds from $P_{r}$ and $R_{r}$ with $p_{r} = ⌈ ϵ^{- 5} 2^{k_{r} + 5} ⌉$ . Its hypothesis $k_{r} p_{r} \leq n$ holds because $k_{r} \leq m_{r}$ makes $k_{r} p_{r} \leq m_{r + 1} \leq M \leq n$ . So $P_{r + 1}$ is equitable, refines $P_{r}$ and hence $P_{0}$ , has $k_{r + 1} = k_{r} p_{r}$ parts with $m_{0} \leq k_{r} \leq k_{r + 1} \leq m_{r + 1}$ , and step 3.1 gives $q (P_{r + 1}) > q (P_{r}) + ϵ^{5} / 2$ .

step 1.1step 1.2step 3.1L1induction

5.1

If none of $P_{0}, \dots, P_{R - 1}$ were $ϵ$ -regular, iterating step 4.1 would produce $P_{R}$ with $q (P_{R}) > q (P_{0}) + R ϵ^{5} / 2 \geq 2 ϵ^{- 5} \cdot ϵ^{5} / 2 = 1$ , contradicting the bound $q \leq 1$ of [L2].

step 4.1L2inductionalgebra

6.1

Hence some $P_{r}$ with $r < R$ is $ϵ$ -regular, and step 4.1 makes it equitable with $k_{r}$ parts satisfying $m_{0} \leq k_{r} \leq m_{r} \leq M$ . That is the asserted partition.

step 4.1step 5.1L3∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

A prescribed finite vertex partition has a bounded $ϵ$ -regular refinement, equitable when the initial partition is equitable

Statement

For every $0 < ϵ < 1$ and $k_{0} \geq 1$ there is $K = K (ϵ, k_{0})$ such that every partition $P_{0}$ of a finite graph into at most $k_{0}$ nonempty parts has an $ϵ$ -regular refinement $P$ into at most $K$ parts. If $P_{0}$ is equitable, $P$ may also be chosen equitable.

Facts & Assumptions

Given: $ϵ, k_{0}$ , a finite graph, and a partition $P_{0}$ as in the Statement.

[L1]

Every nonregular $k$ -part partition has a refinement with at most $k 2^{k + 1}$ parts and energy gain greater than $ϵ^{5}$ (Every nonregular $k$ -part partition has a refinement with energy gain greater than $ϵ^{5}$ and at most $k 2^{k + 1}$ parts).

[L2]

Energy is nondecreasing under refinement and at most $1$ (Energy lies in $[0, 1]$ and cannot decrease under refinement).

[L3]

An equitable partition has part sizes differing by at most one; a partition is $ϵ$ -regular when its irregular ordered pairs carry total weight at most $ϵ n^{2}$ ; and the empty family, the unique partition of the null graph, is equitable and $ϵ$ -regular by convention ( $ϵ$ -regular vertex partitions, equitable partitions, and refinement).

[L4]

[L5]

$(X, Y)$ is $ϵ$ -regular when every $A \subseteq X$ and $B \subseteq Y$ with $∣ A ∣ \geq ϵ ∣ X ∣$ and $∣ B ∣ \geq ϵ ∣ Y ∣$ satisfies $∣ d (A, B) - d (X, Y) ∣ \leq ϵ$ ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · direct

1.1

Arbitrary refinement. Starting from $P_{0}$ , apply [L1] whenever the current partition is not $ϵ$ -regular; each application raises the energy by more than $ϵ^{5}$ and replaces the part-count bound $k$ by $k 2^{k + 1}$ . By [L2] the energy lies in $[0, 1]$ , so at most $⌈ ϵ^{- 5} ⌉$ applications occur, and iterating that map $⌈ ϵ^{- 5} ⌉$ times from $k_{0}$ bounds the number of parts of the resulting $ϵ$ -regular refinement of $P_{0}$ .

givenL1L2inductionalgebra

1.2

Constants for the equitable case. Put $K_{0} = k_{0}$ , $K_{r + 1} = K_{r} ⌈ ϵ^{- 5} 2^{K_{r} + 5} ⌉$ , $R = ⌈ 2 ϵ^{- 5} ⌉$ , and $T = K_{R}$ . Each factor is at least $1$ , so $K_{0} \leq K_{1} \leq \dots \leq K_{R} = T$ .

givenalgebrachoose

2.1

Small graphs. Assume $P_{0}$ is equitable and $n < T$ . The partition of $V (G)$ into singletons refines $P_{0}$ , is equitable, and has $n < T$ parts. It is $ϵ$ -regular: the only subset of a singleton with at least $ϵ$ times its size is the singleton itself, so every pair of singletons has density difference $0$ in [L5]; for $n = 0$ the convention in [L3] gives the same conclusion.

step 1.2L3L5

2.2

Equitisation. Let $P$ be equitable with $k$ parts, let $R$ refine $P$ with at most $K = k 2^{k + 1}$ parts, put $p = ⌈ ϵ^{- 5} 2^{k + 5} ⌉$ , and suppose $k p \leq n$ . Order $V (G)$ so that each part of $P$ is an interval and each cell of $R$ is an interval inside its part, and cut each part $X$ into $p$ consecutive pieces of sizes $⌊ ∣ X ∣ / p ⌋$ or $⌈ ∣ X ∣ / p ⌉$ . Writing $a = ⌊ n / k ⌋$ and $t = ⌊ a / p ⌋ \geq 1$ , the sizes $∣ X ∣ \in {a, a + 1}$ force $⌊ ∣ X ∣ / p ⌋ \geq t$ and $⌈ ∣ X ∣ / p ⌉ \leq t + 1$ , so every piece has size $t$ or $t + 1$ and the result $P^{'}$ is an equitable refinement of $P$ with exactly $k p$ parts.

step 1.2L3algebraconstruct

3.1

Energy loss. Call a piece dirty when it is not contained in a single cell of $R$ , and let $D$ be the union of the dirty pieces. Each of the at most $K - k$ boundaries between consecutive $R$ -cells of one part lies in exactly one piece, so at most $K$ pieces are dirty, each of size at most $⌈ ∣ X ∣ / p ⌉ \leq 2 ∣ X ∣ / p \leq 4 n / (k p)$ ; hence $∣ D ∣ \leq 4 K n / (k p) = 2^{k + 3} n / p \leq ϵ^{5} n / 4$ . Let $S$ be the common refinement of $P^{'}$ and $R$ . It refines $R$ , so $q (S) \geq q (R)$ by [L2], while every clean piece is already a cell of $S$ , so by [L4] the two energies agree except on ordered pairs with an entry inside $D$ , which carry total weight at most $2 ∣ D ∣ / n$ and squared densities in $[0, 1]$ . Therefore $q (P^{'}) \geq q (S) - 2 ∣ D ∣ / n \geq q (R) - ϵ^{5} / 2$ .

step 2.2L2L4algebra

4.1

Iteration. Assume $P_{0}$ is equitable with $k_{0}^{'} \leq K_{0}$ parts and $n \geq T$ . Given an equitable $P_{r}$ that refines $P_{0}$ , has $k_{r} \leq K_{r}$ parts, and is not $ϵ$ -regular, apply [L1] to get a refinement $R_{r}$ with at most $k_{r} 2^{k_{r} + 1}$ parts and energy gain more than $ϵ^{5}$ , then apply steps 2.2 and 3.1 with $p_{r} = ⌈ ϵ^{- 5} 2^{k_{r} + 5} ⌉$ ; the hypothesis $k_{r} p_{r} \leq n$ holds because $k_{r} \leq K_{r}$ makes $k_{r} p_{r} \leq K_{r + 1} \leq T \leq n$ . The result $P_{r + 1}$ is equitable, refines $P_{r}$ and hence $P_{0}$ , has $k_{r + 1} = k_{r} p_{r} \leq K_{r + 1}$ parts, and satisfies $q (P_{r + 1}) > q (P_{r}) + ϵ^{5} / 2$ .

step 1.2step 2.2step 3.1L1induction

5.1

Since energy lies in $[0, 1]$ by [L2], it cannot gain $ϵ^{5} / 2$ at $R = ⌈ 2 ϵ^{- 5} ⌉$ successive rounds, so some $P_{r}$ with $r < R$ is $ϵ$ -regular; it is equitable, refines $P_{0}$ , and has at most $K_{r} \leq T$ parts.

step 4.1L2algebra

6.1

Let $K$ be the larger of $T$ and the bound supplied by step 1.1; both depend only on $ϵ$ and $k_{0}$ . Step 1.1 proves the first assertion, and steps 2.1 and 5.1 prove the equitable assertion for $n < T$ and for $n \geq T$ respectively.

step 1.1step 2.1step 5.1choose∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Every finite graph has a linearly large $ϵ$ -self-regular vertex subset

Statement

For every $0 < ϵ < 1$ there is $δ = δ (ϵ) > 0$ such that every finite graph $G$ with at least one vertex has a nonempty set $W \subseteq V (G)$ with $∣ W ∣ \geq δ ∣ V (G) ∣$ and $(W, W)$ is $ϵ$ -regular. The hypothesis that $G$ is nonempty cannot be dropped: $ϵ$ -self-regularity is defined only for nonempty vertex sets.

Facts & Assumptions

Given: $0 < ϵ < 1$ and a finite graph $G$ with at least one vertex.

[L1]

For arbitrarily small parameters and prescribed minimum part counts, every sufficiently large graph has a bounded equitable regular partition (Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_{0}$ ).

[L2]

A set $W$ is $ϵ$ -self-regular when every two subsets of $W$ of size at least $ϵ ∣ W ∣$ have density within $ϵ$ of $d (W, W)$ ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · direct

1.1

Choose an integer $s ≫ ϵ^{- 3}$ and divide $[0, 1]$ into $q = ⌈ 8 / ϵ ⌉$ intervals of length at most $ϵ / 8$ . Repeated pigeonhole selection gives an integer $R = R (q, s)$ such that every $q$ -colouring of the pairs of an $R$ -set has a monochromatic $s$ -set: select successively a vertex and a colour occurring on at least a $1 / q$ fraction of its remaining incident pairs, and take the initial set large enough for $s$ selections.

givenchooseinduction

2.1

Choose $ρ > 0$ much smaller than $R^{- 2} ϵ^{3}$ , apply [L1] at parameter $ρ$ and minimum part count much larger than $R / ϵ$ , and let $M$ be the resulting upper bound on the number of parts.

step 1.1L1choose

3.1

In the graph on the partition indices whose edges are the regular cross-pairs, fewer than $2 ρ k^{2}$ pairs are missing by equitability. If every $R$ -set contained a missing pair, double-counting pairs inside $R$ -sets would force at least $(\binom{k}{2}) / (\binom{R}{2})$ missing pairs, contrary to the choice of $ρ$ . Hence there is an $R$ -set of indices all of whose cross-pairs are $ρ$ -regular.

step 2.1L1algebra

4.1

Colour those regular pairs by the interval containing their density. Step 1.1 supplies $s$ parts $V_{1}, \dots, V_{s}$ whose cross-densities all lie in one interval; let $W = V_{1} \cup \dots \cup V_{s}$ . Since the partition is equitable and has at most $M$ parts, $∣ W ∣ \geq s n / (2 M)$ .

step 1.1step 3.1choosealgebra

5.1

Let $A, B \subseteq W$ have size at least $ϵ ∣ W ∣$ , and write $A_{i} = A \cap V_{i}$ , $B_{j} = B \cap V_{j}$ . Pairs with $i = j$ , or with $∣ A_{i} ∣ < ρ ∣ V_{i} ∣$ or $∣ B_{j} ∣ < ρ ∣ V_{j} ∣$ , contribute at most $3 / (ϵ^{2} s) + 4 ρ / ϵ$ to the normalized density comparison.

step 2.1step 4.1algebra

6.1

On every remaining pair, regularity gives $∣ d (A_{i}, B_{j}) - d (V_{i}, V_{j}) ∣ \leq ρ$ , while the density colour in step 4.1 makes any two cross-densities differ by at most $ϵ / 8$ . Decomposing both $d (A, B)$ and $d (W, W)$ over the $s^{2}$ pairs and using step 5.1 therefore gives $∣ d (A, B) - d (W, W) ∣ \leq ϵ$ by the choices of $s$ and $ρ$ .

step 4.1step 5.1L2algebra

7.1

For graphs large enough for [L1], steps 4.1 and 6.1 give an $ϵ$ -self-regular $W$ of size at least $s n / (2 M)$ . For the finitely many smaller orders $n \geq 1$ , a singleton is $0$ -self-regular and hence $ϵ$ -self-regular. Shrinking $δ$ to the minimum of $s / (2 M)$ and the reciprocals of those orders proves the Statement for every finite graph with at least one vertex.

step 2.1step 4.1step 6.1L1L2choose∎

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Every finite graph has a bounded partition into self-regular vertex sets

Statement

For every $0 < ϵ < 1$ there is $K = K (ϵ)$ such that the vertex set of every finite graph can be partitioned into at most $K$ sets, each of which is $ϵ$ -self-regular.

Facts & Assumptions

Given: $0 < ϵ < 1$ and a finite graph $G$ .

[L1]

At every smaller regularity parameter, every finite graph with at least one vertex has a nonempty self-regular set containing a fixed positive fraction of its vertices (Every finite graph has a linearly large $ϵ$ -self-regular vertex subset).

[L2]

Given $ϵ^{'} < ϵ$ , sufficiently small vertex and edge changes preserve regularity with parameter $ϵ$ (Regularity survives sufficiently small changes of vertices and cross-edges).

Proof

technique · direct

1.1

Apply [L2] with old parameter $ϵ / 2$ and new parameter $ϵ$ , and let $τ > 0$ be a permitted relative vertex-change fraction. Let $δ > 0$ be supplied by [L1] at parameter $ϵ / 2$ .

givenL1L2choose

2.1

Repeatedly apply [L1] to the graph induced by the vertices not yet chosen, stopping if that remainder is empty and otherwise removing an $(ϵ / 2)$ -self-regular set of at least a $δ$ fraction of it. Choose a fixed $r$ with $(1 - δ)^{r} \leq τ / (1 + τ)$ . After at most $r$ rounds, the unassigned remainder has size at most $τ$ times the size of the union of the extracted sets.

step 1.1L1inductionalgebra

3.1

Distribute every remaining vertex among the at most $r$ extracted sets proportionally to their sizes. For all sufficiently large graph orders, rounding can be absorbed by replacing $τ$ in step 1.1 with a smaller constant, so no set grows by more than the vertex-change fraction allowed by [L2]. No old incidence among vertices of an extracted set is changed.

step 2.1L2choosealgebra

4.1

By [L2], every enlarged set is $ϵ$ -self-regular. Empty and bounded exceptional graphs may instead be partitioned into singletons, increasing the uniform bound only by a constant; hence some $K (ϵ)$ works for all finite graphs.

step 3.1L2induction∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Triangle counting lemma for three pairwise regular vertex sets

Statement

Let $X, Y, Z$ be pairwise disjoint nonempty vertex sets such that all three cross-pairs are $ϵ$ -regular. Write $d (X, Y) = a, d (X, Z) = b, d (Y, Z) = c,$ and suppose $a, b \geq 2 ϵ$ . Then the number of ordered triples $(x, y, z) \in X \times Y \times Z$ spanning a triangle is at least $(1 - 2 ϵ) (a - ϵ) (b - ϵ) (c - ϵ) ∣ X ∣ ∣ Y ∣ ∣ Z ∣ .$ When $c < ϵ$ , the right side is nonpositive and the inequality is interpreted literally.

Facts & Assumptions

Given: Three vertex sets satisfying the hypotheses in the Statement.

[L1]

In an $ϵ$ -regular pair $(X, Y)$ of density $d$ , and for $Y^{'} \subseteq Y$ with $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ , fewer than $ϵ ∣ X ∣$ vertices $x \in X$ have $∣ N (x) \cap Y^{'} ∣ < (d - ϵ) ∣ Y^{'} ∣$ , and separately fewer than $ϵ ∣ X ∣$ have $∣ N (x) \cap Y^{'} ∣ > (d + ϵ) ∣ Y^{'} ∣$ (In a regular pair, fewer than $ϵ ∣ X ∣$ vertices have too small a degree into a large subset, and fewer than $ϵ ∣ X ∣$ have too large a degree).

[L2]

If $(Y, Z)$ is $ϵ$ -regular, then any subsets of sizes at least $ϵ ∣ Y ∣$ and $ϵ ∣ Z ∣$ have density at least $d (Y, Z) - ϵ$ ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · direct

1.1

By [L1], fewer than $ϵ ∣ X ∣$ vertices have fewer than $(a - ϵ) ∣ Y ∣$ neighbours in $Y$ , and fewer than $ϵ ∣ X ∣$ have fewer than $(b - ϵ) ∣ Z ∣$ neighbours in $Z$ . Thus at least $(1 - 2 ϵ) ∣ X ∣$ vertices $x \in X$ satisfy both lower bounds.

givenL1algebra

2.1

For each such $x$ , put $Y_{x} = N (x) \cap Y$ and $Z_{x} = N (x) \cap Z$ . Since $a, b \geq 2 ϵ$ , step 1.1 gives $∣ Y_{x} ∣ \geq ϵ ∣ Y ∣$ and $∣ Z_{x} ∣ \geq ϵ ∣ Z ∣$ .

step 1.1algebra

3.1

By [L2], there are at least $(c - ϵ) ∣ Y_{x} ∣ ∣ Z_{x} ∣$ edges between $Y_{x}$ and $Z_{x}$ , and each produces a unique triangle $(x, y, z)$ .

step 2.1L2

4.1

Since $a \leq 1$ and $a \geq 2 ϵ$ , we have $ϵ \leq 1 / 2$ , so $1 - 2 ϵ \geq 0$ . If $c < ϵ$ then $c - ϵ < 0$ makes the claimed lower bound nonpositive, while the triangle count is nonnegative, so the inequality holds. If $c \geq ϵ$ then $c - ϵ \geq 0$ , so substituting the bounds $∣ Y_{x} ∣ \geq (a - ϵ) ∣ Y ∣$ and $∣ Z_{x} ∣ \geq (b - ϵ) ∣ Z ∣$ of step 1.1 into $(c - ϵ) ∣ Y_{x} ∣ ∣ Z_{x} ∣$ preserves the inequality of step 3.1; summing over the at least $(1 - 2 ϵ) ∣ X ∣$ good choices of $x$ gives exactly the claimed product bound.

step 1.1step 3.1algebra∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Counting lemma: regular dense pairs contain many part-respecting copies of every fixed graph

Statement

Let $H$ be a finite simple graph on labelled vertices $[h]$ , and let $0 < η < 1$ . There are constants $γ = γ (H, η) > 0$ , $c = c (H, η) > 0$ , and $N = N (H, η)$ such that the following holds for every finite simple graph $G$ . Let $W_{1}, \dots, W_{h} \subseteq V (G)$ be nonempty, not necessarily distinct, with $∣ W_{i} ∣ \geq N$ . Whenever $i j \in E (H)$ , require $W_{i} \neq W_{j}$ and require $(W_{i}, W_{j})$ to be $γ$ -regular in $G$ of density at least $η$ . Then at least $c \prod_{i = 1}^{h} ∣ W_{i} ∣$ maps $ϕ : [h] \to V (G)$ with $ϕ (i) \in W_{i}$ carry every edge of $H$ to an edge of $G$ . At least half this many such maps are injective, after increasing $N$ if necessary.

Facts & Assumptions

Given: $H, η$ , a host graph $G$ , and host sets $W_{i} \subseteq V (G)$ satisfying the Statement.

[L1]

If $(X, Y)$ is $ϵ$ -regular of density $d$ and $Y^{'} \subseteq Y$ satisfies $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ , then fewer than $ϵ ∣ X ∣$ vertices $x \in X$ have $∣ N (x) \cap Y^{'} ∣ < (d - ϵ) ∣ Y^{'} ∣$ , and separately fewer than $ϵ ∣ X ∣$ have $∣ N (x) \cap Y^{'} ∣ > (d + ϵ) ∣ Y^{'} ∣$ (In a regular pair, fewer than $ϵ ∣ X ∣$ vertices have too small a degree into a large subset, and fewer than $ϵ ∣ X ∣$ have too large a degree).

[L2]

Restricting a regular pair to sufficiently large subsets preserves regularity, with a controlled new parameter and density loss (Slicing lemma: large subpairs remain regular and their density shifts by at most $ϵ$ ).

[L3]

A finite simple graph has finitely many vertices, no loops, and unordered edges between distinct vertices (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

Proof

technique · direct

1.1

If $h = 0$ there is exactly one map $ϕ : \emptyset \to V (G)$ , it is injective and carries every edge of $H$ to an edge of $G$ vacuously, and $\prod_{i = 1}^{0} ∣ W_{i} ∣ = 1$ , so $γ = c = 1 / 2$ and $N = 1$ give both assertions; assume $h \geq 1$ from here. Put $e = ∣ E (H) ∣$ . Choose $γ > 0$ with $γ \leq (η / 2)^{h} / (2 h)$ ; since $h \geq 1$ and $0 < η < 1$ this also gives $γ \leq (η / 2)^{h}$ and $γ \leq η / 2$ . Set $c = 2^{- h} (η / 2)^{e} > 0$ .

givenL3choose

2.1

Embed the vertices in the order $1, \dots, h$ . After choosing images for $1, \dots, r$ , maintain for each $j > r$ the candidate set obtained by intersecting $W_{j}$ with the neighbourhoods of the already embedded neighbours of $j$ . The invariant is $∣ C_{j} ∣ \geq (η / 2)^{d_{r} (j)} ∣ W_{j} ∣$ , where $d_{r} (j)$ is the number of neighbours of $j$ among $[r]$ .

step 1.1induction

3.1

Suppose the invariant holds before embedding $r + 1$ , and let $j > r + 1$ be a neighbour of $r + 1$ . The invariant and step 1.1 give $∣ C_{j} ∣ \geq (η / 2)^{h} ∣ W_{j} ∣ \geq γ ∣ W_{j} ∣$ , so $C_{j}$ meets the size threshold [L1] asks of a subset of $W_{j}$ inside the original $γ$ -regular pair $(W_{r + 1}, W_{j})$ ; no reslicing of that pair is needed for this bound, and [L2] confirms that the restricted pairs carried along remain regular. Write $d$ for the density of $(W_{r + 1}, W_{j})$ , so $d \geq η$ . Applying [L1] to this one subset $C_{j}$ , fewer than $γ ∣ W_{r + 1} ∣$ vertices of $W_{r + 1}$ have fewer than $(d - γ) ∣ C_{j} ∣$ neighbours in $C_{j}$ , and $(d - γ) ∣ C_{j} ∣ \geq (η - γ) ∣ C_{j} ∣ \geq (η / 2) ∣ C_{j} ∣$ because $γ \leq η / 2$ . This is a bound for the single subset $C_{j}$ , giving one exceptional set for each neighbour of $r + 1$ .

step 1.1step 2.1L1L2

4.1

The union of the at most $h$ exceptional sets of step 3.1 has size at most $h γ ∣ W_{r + 1} ∣ \leq \frac{1}{2} (η / 2)^{h} ∣ W_{r + 1} ∣ \leq \frac{1}{2} ∣ C_{r + 1} ∣$ , so at least half of $C_{r + 1}$ survives; note that the exceptional sets are measured against $W_{r + 1}$ , not against $C_{r + 1}$ . Every remaining choice preserves the invariant after replacing each future-neighbour candidate set by its neighbourhood. Vertex $v$ is therefore chosen from a set of size at least $\frac{1}{2} (η / 2)^{d_{v - 1} (v)} ∣ W_{v} ∣$ , and $\sum_{v} d_{v - 1} (v) = e$ because each edge is counted once, at its later endpoint. Thus the greedy induction supplies at least $2^{- h} (η / 2)^{e} \prod_{i} ∣ W_{i} ∣ = c \prod_{i} ∣ W_{i} ∣$ edge-preserving maps.

step 1.1step 2.1step 3.1inductionalgebra

5.1

A noninjective map identifies at least one pair $i < j$ and hence there are at most $(\binom{h}{2}) N^{- 1} \prod_{i} ∣ W_{i} ∣$ collision choices. Choose $N$ so that this is at most $(c / 2) \prod_{i} ∣ W_{i} ∣$ whenever all $∣ W_{i} ∣ \geq N$ .

step 4.1L3algebrachoose

6.1

Removing these collision maps leaves at least $(c / 2) \prod_{i} ∣ W_{i} ∣$ injective part-respecting copies of $H$ .

step 4.1step 5.1∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Induced counting lemma: regular edge and nonedge pairs force many induced copies

Statement

Let $H$ be a graph on labelled vertices $[h]$ and let $0 < η < 1 / 2$ . There are $γ = γ (H, η) > 0$ , $c = c (H, η) > 0$ , and $N = N (H, η)$ such that the following holds. Let $W_{1}, \dots, W_{h}$ be vertex sets of size at least $N$ , with repetitions allowed. Assume every $(W_{i}, W_{j})$ , including those with $W_{i} = W_{j}$ , is $γ$ -regular. If $d (W_{i}, W_{j}) \geq η for i j \in E (H), d (W_{i}, W_{j}) \leq 1 - η for i j \notin E (H),$ then there are at least $c \prod_{i} ∣ W_{i} ∣$ injective maps $ϕ$ with $ϕ (i) \in W_{i}$ that induce $H$ .

Facts & Assumptions

Given: $H, η$ and regular host sets as in the Statement.

[L1]

Regular dense pairs support a greedy count of many part-respecting injective edge-preserving maps of any fixed graph (Counting lemma: regular dense pairs contain many part-respecting copies of every fixed graph).

[L2]

For disjoint sets, complementation preserves the regularity parameter and replaces density $d$ by $1 - d$ (Complementation sends a disjoint $ϵ$ -regular pair of density $d$ to one of density $1 - d$ ).

[L3]

An induced embedding is injective and preserves both adjacency and nonadjacency; its labelled count is ${ind}_{H} (G)$ (Induced embeddings and induced copies of a graph, The induced-embedding count ${ind}_{H} (G)$ ).

Proof

technique · direct

1.1

Colour each unordered pair $i j$ of pattern vertices by whether it is an edge or a nonedge of $H$ . On an edge pair retain adjacency in the host; on a nonedge pair regard nonadjacency as the required relation.

givenL3

2.1

If $W_{i}$ and $W_{j}$ are disjoint, [L2] turns the latter relation into a $γ$ -regular pair of complementary density at least $η$ . If the host sets coincide or overlap, the same conclusion for candidate degrees follows directly from the defining regularity inequalities: replace each density $d (A, B)$ by the proportion of distinct ordered pairs in $A \times B$ that are nonedges. For candidate sets $A \subseteq W_{i}$ and $B \subseteq W_{j}$ the coinciding pairs number $∣ A \cap B ∣$ , so this replacement changes the proportion by at most $∣ A \cap B ∣ / (∣ A ∣ ∣ B ∣) \leq 1 / \max (∣ A ∣, ∣ B ∣)$ — a bound in the current candidate sizes, not in $\min_{i} ∣ W_{i} ∣$ , since candidate sets shrink as the greedy argument proceeds.

step 1.1L2algebra

3.1

Choose $γ$ small enough for the greedy argument underlying [L1] with density threshold $η / 2$ and all $(\binom{h}{2})$ coloured constraints, and let $ρ = ρ (H, η) > 0$ be the fraction of its host set that every candidate set provably retains throughout that argument, so that every candidate set met in step 2.1 has size at least $ρ N$ . Choose $N$ large enough that $1 / (ρ N) < η / 4$ ; then the diagonal error of step 2.1 stays below $η / 4$ at every stage.

step 2.1L1choose

4.1

Run that greedy proof with the required relation for each pair. At each stage the typical-degree exclusions occupy only a controlled fraction of the current candidate set, so at least $c_{0} \prod_{i} ∣ W_{i} ∣$ relation-preserving maps remain for a constant $c_{0} = c_{0} (H, η) > 0$ .

step 3.1L1induction

5.1

At most $(\binom{h}{2}) N^{- 1} \prod_{i} ∣ W_{i} ∣$ of these maps have a collision. Enlarge $N$ so this is below $c_{0} \prod_{i} ∣ W_{i} ∣ / 2$ and put $c = c_{0} / 2$ .

step 4.1algebrachoose

6.1

Every surviving map is injective and realizes adjacency exactly on the edges of $H$ , so it is an induced embedding by [L3]. This proves the claimed bound.

step 1.1step 5.1L3∎

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Graph edit distance and being $ϵ$ -far from an induced-hereditary property

Definition

For two finite simple graphs $G, G^{'}$ on the same vertex set, their edit distance is $dist (G, G^{'}) : = ∣ E (G) △ E (G^{'}) ∣,$ the number of unordered vertex pairs whose adjacency must be changed to turn $G$ into $G^{'}$ . If $G$ has order $n$ and $P$ is a hereditary graph property (Hereditary graph classes), then $G$ is $ϵ$ -far from $P$ when $dist (G, G^{'}) \geq ϵ n^{2}$ for every graph $G^{'} \in P$ on $V (G)$ . Edits may delete edges or add nonedges.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Graph removal lemma for a fixed ordinary subgraph

Statement

For every finite simple graph $H$ and every $ϵ > 0$ there are $δ > 0$ and $n_{0}$ such that the following holds. If a graph $G$ of order $n \geq n_{0}$ has fewer than $δ n^{∣ V (H) ∣}$ injective edge-preserving maps from $H$ to $G$ , then one can delete fewer than $ϵ n^{2}$ edges from $G$ and obtain an $H$ -free graph.

Facts & Assumptions

Given: A fixed graph $H$ , a parameter $ϵ > 0$ , and a sufficiently large graph $G$ .

[L1]

For every $0 < γ < 1$ and every prescribed $m_{0} \geq 1$ there is $M = M (γ, m_{0})$ such that every graph of order $n \geq M$ has an equitable $γ$ -regular vertex partition into $k$ parts with $m_{0} \leq k \leq M$ (Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_{0}$ ).

[L2]

For fixed $H$ , regular pairs of density bounded below contain a positive product-proportion of injective part-respecting copies of $H$ (Counting lemma: regular dense pairs contain many part-respecting copies of every fixed graph).

[L3]

A finite simple graph has no loops or multiple edges, so deleting an edge changes one unordered vertex pair (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

Proof

technique · contraposition

1.1

We prove the contrapositive. Put $h = ∣ V (H) ∣$ , choose $0 < η < 1$ with $η ≪ ϵ$ , then choose a regularity parameter $0 < γ < η$ small enough for [L2], so $0 < γ < 1$ as [L1] requires. Set $m_{0} = ⌈ 8 / ϵ ⌉$ and require $n_{0} \geq \max (M (γ, m_{0}), 8 / ϵ)$ . Apply [L1] at $γ$ with minimum part count $m_{0}$ , obtaining an equitable $γ$ -regular partition into $k$ parts with $m_{0} \leq k \leq M$ .

contrapositive-reducegivenL1L2choose

2.1

From $G$ delete every edge inside a partition part, every edge across a $γ$ -irregular pair, and every edge across a regular pair of density below $η$ . Call the resulting graph $G^{'}$ .

step 1.1choose

3.1

Equitability bounds the within-part deletions by $\sum_{i} ∣ V_{i} ∣^{2} \leq n \max_{i} ∣ V_{i} ∣ \leq n (n / k + 1) = n^{2} / k + n$ , and $k \geq m_{0} \geq 8 / ϵ$ together with $n \geq n_{0} \geq 8 / ϵ$ make this at most $ϵ n^{2} / 4$ by [L1]; $γ$ -regularity bounds the irregular-pair deletions by $γ n^{2}$ ; and the low-density pairs contribute at most $η n^{2}$ . Choose $γ, η$ so that $γ + η < ϵ / 2$ . Hence fewer than $ϵ n^{2}$ edges were deleted, each changing one unordered vertex pair by [L3].

step 1.1step 2.1L1L3algebra

4.1

Assume that fewer than $ϵ n^{2}$ deletions cannot make $G$ $H$ -free. Then $G^{'}$ contains a copy of $H$ . Assign to each vertex of $H$ the partition part containing its image. Every edge of $H$ lies across a $γ$ -regular pair of density at least $η$ .

assume-hypstep 2.1step 3.1

5.1

Apply [L2] to those assigned parts. Since each has size at least $n / (2 M)$ for the fixed regularity bound $M$ , the original graph contains at least $c \prod_{i = 1}^{h} ∣ W_{i} ∣ \geq c (2 M)^{- h} n^{h}$ injective copies of $H$ . Put $δ = c (2 M)^{- h}$ .

step 4.1L2algebra

6.1

Thus every graph requiring at least $ϵ n^{2}$ edge deletions contains at least $δ n^{h}$ copies of $H$ , which is the contrapositive of the Statement.

step 1.1step 5.1discharge-contrapositive∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Equitable strong regularity lemma: a very regular refinement that changes energy only slightly

Statement

Let $ϵ_{0} \geq ϵ_{1} \geq ϵ_{2} \geq \dots > 0$ and let $m_{0} \geq 1$ . There is $M = M ((ϵ_{i}), m_{0})$ such that every finite graph $G$ with $∣ V (G) ∣ \geq m_{0}$ has equitable partitions $P, Q$ satisfying

$Q$ refines $P$ ;
$P$ is $ϵ_{0}$ -regular;
$Q$ is $ϵ_{∣ P ∣}$ -regular;
$q (Q) \leq q (P) + ϵ_{0}$ ; and
$m_{0} \leq ∣ P ∣$ and $∣ Q ∣ \leq M$ .

Facts & Assumptions

Given: A nonincreasing positive sequence $(ϵ_{i})_{i \geq 0}$ , an integer $m_{0} \geq 1$ , and a finite graph $G$ of order $n \geq m_{0}$ .

[L1]

For every $0 < ϵ < 1$ and $k_{0} \geq 1$ there is $K (ϵ, k_{0})$ such that every partition into at most $k_{0}$ nonempty parts has an $ϵ$ -regular refinement into at most $K$ parts, which may be chosen equitable when the given partition is equitable (A prescribed finite vertex partition has a bounded $ϵ$ -regular refinement, equitable when the initial partition is equitable).

[L2]

For every $0 < ϵ < 1$ and $m_{0} \geq 1$ there is $M_{0} (ϵ, m_{0})$ such that every graph of order at least $M_{0}$ has an equitable $ϵ$ -regular partition into $k$ parts with $m_{0} \leq k \leq M_{0}$ (Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_{0}$ ).

[L3]

Energy is nondecreasing under refinement and lies in $[0, 1]$ (Energy lies in $[0, 1]$ and cannot decrease under refinement).

[L4]

An equitable partition has part sizes differing by at most one, and a partition is $ϵ$ -regular when its irregular ordered pairs carry total weight at most $ϵ n^{2}$ ( $ϵ$ -regular vertex partitions, equitable partitions, and refinement).

[L5]

Proof

technique · direct

1.1

If $ϵ \leq ϵ^{'}$ then every $ϵ$ -regular pair is $ϵ^{'}$ -regular, because the subsets tested at parameter $ϵ^{'}$ are among those tested at $ϵ$ ; by [L4] the same monotonicity passes to partitions. So replacing each $ϵ_{i}$ by $\min (ϵ_{i}, 1 / 2)$ keeps the sequence positive and nonincreasing and only strengthens every conclusion, and we may assume $ϵ_{i} < 1$ for all $i$ . Let $M_{0} = M_{0} (ϵ_{0}, m_{0})$ be the constant of [L2].

givenL2L4L5choose

2.1

Small graphs. Suppose $m_{0} \leq n < M_{0}$ and let $P = Q$ be the partition of $V (G)$ into singletons. It refines itself, is equitable, and has $n \geq m_{0}$ parts. The only subset of a singleton of size at least $ϵ$ times its size is the singleton itself, so by [L5] every pair of singletons is $ϵ$ -regular for every $ϵ > 0$ , giving conclusions 2 and 3; and $q (Q) = q (P)$ gives conclusion 4.

step 1.1L4L5

2.2

Large graphs. Suppose $n \geq M_{0}$ . Use [L2] to choose an equitable $ϵ_{0}$ -regular partition $P_{0}$ with $m_{0} \leq ∣ P_{0} ∣ \leq M_{0}$ . Having constructed $P_{i}$ , apply [L1] to $P_{i}$ with parameter $ϵ_{∣ P_{i} ∣}$ to choose an equitable refinement $P_{i + 1}$ that is $ϵ_{∣ P_{i} ∣}$ -regular.

step 1.1L1L2inductionchoose

3.1

Each part count is bounded by a function of the preceding one and the fixed sequence, so for every fixed number of stages all $∣ P_{i} ∣$ are bounded independently of $G$ . A refinement has at least as many parts as the partition it refines, so $∣ P_{i} ∣ \geq ∣ P_{0} ∣ \geq m_{0}$ for every $i$ .

step 2.2L1induction

3.2

Set $R = ⌈ 1 / ϵ_{0} ⌉ + 1$ . If $q (P_{i + 1}) > q (P_{i}) + ϵ_{0}$ for every $i < R$ , telescoping would give $q (P_{R}) > 1$ , contrary to [L3]. Hence some $i < R$ satisfies $q (P_{i + 1}) \leq q (P_{i}) + ϵ_{0}$ ; put $P = P_{i}$ and $Q = P_{i + 1}$ .

step 2.2L3algebrachoose

4.1

Step 2.2 supplies refinement, equitability, and $ϵ_{∣ P ∣}$ -regularity of $Q$ . Also $P$ is $ϵ_{0}$ -regular: this holds for $P_{0}$ by construction, and every later $P_{i}$ is $ϵ_{∣ P_{i - 1} ∣}$ -regular with $ϵ_{∣ P_{i - 1} ∣} \leq ϵ_{0}$ , which gives $ϵ_{0}$ -regularity by step 1.1. Step 3.1 gives $∣ P ∣ \geq m_{0}$ and step 3.2 the energy bound.

step 1.1step 2.2step 3.1step 3.2algebra

5.1

Let $M$ be the largest of $M_{0}$ and the recursively obtained part-count bounds through stage $R$ . Step 2.1 settles $n < M_{0}$ and steps 3.1 and 4.1 settle $n \geq M_{0}$ , so in both cases $∣ Q ∣ \leq M$ and all five conclusions hold.

step 2.1step 3.1step 4.1∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

A small energy increment makes fine-pair densities close to their coarse densities almost everywhere

Statement

Let $Q$ refine a vertex partition $P$ of an $n$ -vertex graph. For $x, y \in V (G)$ , let $P_{x}, P_{y}$ be their $P$ -parts and $Q_{x}, Q_{y}$ their $Q$ -parts. If $q (Q) - q (P) \leq ϵ^{3},$ then fewer than or equal to $ϵ n^{2}$ ordered pairs $(x, y)$ satisfy $∣ d (Q_{x}, Q_{y}) - d (P_{x}, P_{y}) ∣ > ϵ .$

Facts & Assumptions

Given: Partitions and a parameter satisfying the Statement.

[L1]

Energy is the weighted mean square of part-pair densities, and refinement cannot lower it (The mean-square density, or energy, of a vertex partition, Energy lies in $[0, 1]$ and cannot decrease under refinement).

[L2]

For a nonnegative finite random variable $X$ and $a > 0$ , Markov's inequality gives $\Pr (X \geq a) \leq E X / a$ (Markov's inequality on a finite probability space).

Proof

technique · direct

1.1

Choose an ordered vertex pair $(x, y)$ uniformly and set $Z_{P} = d (P_{x}, P_{y})$ and $Z_{Q} = d (Q_{x}, Q_{y})$ . On each coarse pair, double-counting gives $E (Z_{Q} ∣ P_{x}, P_{y}) = Z_{P}$ .

givenL1algebra

2.1

Expanding the square and using the conditional identity in step 1.1 gives $E ((Z_{Q} - Z_{P})^{2}) = E (Z_{Q}^{2}) - E (Z_{P}^{2}) = q (Q) - q (P) \leq ϵ^{3} .$

step 1.1L1algebra

3.1

Apply [L2] to $(Z_{Q} - Z_{P})^{2}$ with threshold $ϵ^{2}$ . The probability that $∣ Z_{Q} - Z_{P} ∣ > ϵ$ is at most $ϵ^{3} / ϵ^{2} = ϵ$ .

step 2.1L2algebra

4.1

Multiplying this probability by the $n^{2}$ ordered vertex pairs proves the asserted exceptional-pair bound.

step 3.1algebra∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Strong regularity with linearly large representative subsets and no irregular representative pair

Statement

Let $ϵ_{0} > 0$ , let $ϵ_{1} \geq ϵ_{2} \geq \dots > 0$ , and let $k_{0} \geq 1$ . There are $K$ and $δ > 0$ such that every finite graph $G$ of order at least $k_{0}$ has an equitable partition $V (G) = V_{1} ⊔ \dots ⊔ V_{k}, k_{0} \leq k \leq K,$ and nonempty subsets $W_{i} \subseteq V_{i}$ with $∣ W_{i} ∣ \geq δ ∣ V (G) ∣$ such that

every pair $(W_{i}, W_{j})$ , including $i = j$ , is $ϵ_{k}$ -regular; and
for all but at most $ϵ_{0} k^{2}$ ordered pairs $(i, j)$ , $∣ d (W_{i}, W_{j}) - d (V_{i}, V_{j}) ∣ \leq ϵ_{0} .$

Facts & Assumptions

Given: $ϵ_{0}$ , a nonincreasing positive sequence, an integer $k_{0} \geq 1$ , and a finite graph $G$ of order $n \geq k_{0}$ .

[L1]

For any prescribed minimum coarse part count $m_{0}$ , strong regularity produces equitable partitions $P, Q$ of any graph of order at least $m_{0}$ with $Q$ refining $P$ , $P$ being $ϵ_{0}$ -regular with $m_{0} \leq ∣ P ∣$ , $Q$ being $ϵ_{∣ P ∣}$ -regular, $q (Q) \leq q (P) + ϵ_{0}$ , and $∣ Q ∣$ bounded (Equitable strong regularity lemma: a very regular refinement that changes energy only slightly).

[L2]

A small energy increment makes almost all fine-pair densities close to their coarse densities (A small energy increment makes fine-pair densities close to their coarse densities almost everywhere).

[L3]

Every finite graph with at least one vertex contains a nonempty linearly large self-regular subset at any prescribed parameter (Every finite graph has a linearly large $ϵ$ -self-regular vertex subset).

[L4]

Large restrictions of regular pairs stay regular and have nearby density (Slicing lemma: large subpairs remain regular and their density shifts by at most $ϵ$ ).

[L5]

If a nonnegative integer-valued random variable has expectation below $1$ , some outcome makes it zero (The first-moment method for avoiding or forcing a finite count of bad events).

Proof

technique · constructive

1.1

Apply [L1] with minimum coarse part count $m_{0} = k_{0}$ , coarse parameter much smaller than $ϵ_{0}^{3}$ , and fine parameter, at a coarse part count $k$ , much smaller than $ϵ_{k}$ after slicing. This is legitimate because $n \geq k_{0}$ . Obtain equitable $P = {V_{1}, \dots, V_{k}}$ with $k_{0} \leq k \leq K$ and a fine equitable refinement $Q$ .

givenL1chooseconstruct

2.1

By [L2], the total ordered vertex-pair weight of fine pairs whose density differs from their coarse pair by more than $ϵ_{0} / 2$ is at most a chosen constant below $ϵ_{0}^{2}$ . The fine partition has bounded order.

step 1.1L2algebra

3.1

Independently for each $i$ , choose a fine atom $U_{i} \subseteq V_{i}$ with probability proportional to its size. Choose the parameters so that the expected number $I$ of nonregular selected ordered pairs is below $1 / 4$ , while the expected number $D$ of pairs with $∣ d (U_{i}, U_{j}) - d (V_{i}, V_{j}) ∣ > ϵ_{0} / 2$ is below $ϵ_{0} k^{2} / 4$ .

step 1.1step 2.1algebra

4.1

Inside every selected atom $U_{i}$ , apply [L3] at a much smaller parameter and obtain $W_{i} \subseteq U_{i}$ of size at least a fixed fraction of $∣ U_{i} ∣$ . Because both partition orders are bounded and equitable, there is a uniform $δ > 0$ with $∣ W_{i} ∣ \geq δ n$ .

step 3.1L3choose

4.2

Let $X = I + 1_{{D > ϵ_{0} k^{2}}}$ . Since $1_{{D > ϵ_{0} k^{2}}} \leq D / (ϵ_{0} k^{2})$ , step 3.1 gives $E X < 1 / 2$ . By [L5] there is a selection with $X = 0$ : it has no irregular selected pair and at most $ϵ_{0} k^{2}$ density failures.

step 3.1L5algebrachoose

5.1

On every fine-regular selected cross-pair, [L4] makes $(W_{i}, W_{j})$ $ϵ_{k}$ -regular and changes its density by at most $ϵ_{0} / 2$ . Each diagonal pair is $ϵ_{k}$ -regular by the self-regular choice in step 4.1.

step 3.1step 4.1L4algebra

6.1

For that selection, step 5.1 gives regularity for every representative pair, while step 4.2 gives the density-approximation exception bound. Step 4.1 gives the common linear lower bound and makes each $W_{i}$ nonempty, and step 1.1 gives $k_{0} \leq k \leq K$ , completing the construction.

step 4.1step 5.1step 4.2discharge-construct∎

RemarkRemark: Literature-sourcedProof: Not applicableaudited 2026-08-16Open item page →

Ordinary regularity gives tower upper bounds; strong regularity gives wowzer upper bounds only when the regularity sequence depends on the coarse part count

Remark

The energy-increment proof of ordinary regularity in Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_{0}$ iterates an exponential part-count recurrence only a bounded number of times and therefore gives a tower-type upper bound. The proof of Equitable strong regularity lemma: a very regular refinement that changes energy only slightly repeatedly invokes ordinary regularity at parameters indexed by an already enormous partition size, so when the regularity sequence genuinely depends on the coarse part count the nested iteration gives a wowzer-type upper bound. That dependence is what Induced graph removal lemma for a fixed graph does not need: the parameter it requires of its representative pairs comes from Induced counting lemma: regular edge and nonedge pairs force many induced copies and depends only on the pattern and the density threshold, so a constant sequence suffices, the nesting collapses to boundedly many applications at one fixed parameter, and the bound stays tower-type. These are upper bounds delivered by the displayed proofs, not claims of optimality.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Induced graph removal lemma for a fixed graph

Statement

For every finite graph $H$ and every $ϵ > 0$ there are $δ > 0$ and $n_{0}$ such that every graph $G$ of order $n \geq n_{0}$ satisfying ${ind}_{H} (G) < δ n^{∣ V (H) ∣}$ can be changed into an induced- $H$ -free graph by adding or deleting fewer than $ϵ n^{2}$ edges. Equivalently, every graph that is $ϵ$ -far from being induced- $H$ -free contains at least $δ n^{∣ V (H) ∣}$ labelled induced copies of $H$ .

Facts & Assumptions

Given: A fixed graph $H$ , $ϵ > 0$ , and a sufficiently large graph $G$ .

[L1]

For any prescribed minimum part count $k_{0}$ , every graph of order at least $k_{0}$ has an equitable partition into $k$ parts with $k_{0} \leq k \leq K$ , carrying nonempty representative subsets $W_{i} \subseteq V_{i}$ of size at least $δ n$ , such that every representative pair, including self-pairs, is very regular and all but at most $ϵ_{0} k^{2}$ ordered representative densities approximate their coarse densities (Strong regularity with linearly large representative subsets and no irregular representative pair).

[L2]

Regular pairs whose edge and nonedge densities stay away from the wrong extremes force a positive product-proportion of induced embeddings of $H$ (Induced counting lemma: regular edge and nonedge pairs force many induced copies).

[L3]

Edit distance counts added and deleted adjacencies, and $ϵ$ -far means that every graph in the target hereditary property is at distance at least $ϵ n^{2}$ (Graph edit distance and being $ϵ$ -far from an induced-hereditary property).

[L4]

The number ${ind}_{H} (G)$ counts labelled induced embeddings of $H$ in $G$ (The induced-embedding count ${ind}_{H} (G)$ ).

Proof

technique · contraposition

1.1

We prove the equivalent far-from-free formulation. Choose $0 < η ≪ ϵ$ , require $n_{0} \geq 8 / ϵ$ , and apply [L1] with minimum part count $k_{0} = ⌈ 8 / ϵ ⌉$ and with density-approximation error and regularity sequence small enough for [L2]. Write the resulting coarse parts as $V_{1}, \dots, V_{k}$ , so that $k \geq 8 / ϵ$ , and the representatives as $W_{1}, \dots, W_{k}$ .

contrapositive-reducegivenL1L2choose

2.1

Construct $G^{'}$ from $G$ as follows for every unordered coarse pair, allowing a pair with equal indices. If $d (W_{i}, W_{j}) < η$ , delete all corresponding edges; if $d (W_{i}, W_{j}) > 1 - η$ , add all corresponding nonedges; otherwise leave those adjacencies unchanged.

step 1.1choose

3.1

For every coarse pair whose representative and coarse densities differ by at most the approximation error, the number of edits is at most $(η + o (1)) ∣ V_{i} ∣ ∣ V_{j} ∣$ . Exceptional pairs have total count at most $o (k^{2})$ , and equitability controls their weight. The diagonal pairs are edited without any density control, but equitability bounds their total contribution by $\sum_{i} ∣ V_{i} ∣^{2} \leq n \max_{i} ∣ V_{i} ∣ \leq n (n / k + 1) = n^{2} / k + n$ , which the choices $k \geq 8 / ϵ$ and $n \geq n_{0} \geq 8 / ϵ$ of step 1.1 make at most $ϵ n^{2} / 4$ . The choices in step 1.1 therefore make $dist (G, G^{'}) < ϵ n^{2}$ .

step 1.1step 2.1L1L3algebra

4.1

Assume that $G$ is $ϵ$ -far from induced- $H$ -free. Then [L3] and step 3.1 imply that $G^{'}$ contains an induced copy of $H$ . For each pattern vertex $a$ , let $i (a)$ be the coarse part containing its image. Repetitions among the indices are allowed.

assume-hypstep 3.1L3choose

5.1

If $a b \in E (H)$ , the cleaning rule and the edge of this copy imply $d (W_{i (a)}, W_{i (b)}) \geq η$ . If $a b \notin E (H)$ , its nonedge implies $d (W_{i (a)}, W_{i (b)}) \leq 1 - η$ . Every such representative pair is regular, including when $i (a) = i (b)$ , by [L1].

step 2.1step 4.1L1

6.1

Apply [L2] to $W_{i (1)}, \dots, W_{i (h)}$ . Since every representative has size at least $ρ n$ for a constant $ρ > 0$ , the original graph $G$ contains at least $c \prod_{a = 1}^{h} ∣ W_{i (a)} ∣ \geq c ρ^{h} n^{h}$ induced embeddings of $H$ . Set $δ = c ρ^{h}$ .

step 5.1L2L4algebra

7.1

Thus every $ϵ$ -far graph has at least $δ n^{h}$ induced copies. This is the contrapositive, and hence proves both formulations in the Statement.

step 1.1step 6.1discharge-contrapositive∎

5 · Examples, counterexamples and false statements

None yet.

Sources

Standard references

Recommended treatments; not extraction sources.

Regular Pairs and Induced Counting

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Edge counts and densities between nonempty vertex sets

Definition

ϵϵ-regular pairs and self-regular vertex sets

Definition

Complementation sends a disjoint ϵϵ-regular pair of density dd to one of density 1−d1−d

Statement

Facts & Assumptions

Proof

In a regular pair, fewer than ϵ∣X∣ϵ∣X∣ vertices have too small a degree into a large subset, and fewer than ϵ∣X∣ϵ∣X∣ have too large a degree

Statement

Facts & Assumptions

Proof

Slicing lemma: large subpairs remain regular and their density shifts by at most ϵϵ

Statement

Facts & Assumptions

Proof

Regularity survives sufficiently small changes of vertices and cross-edges

Statement

Facts & Assumptions

Proof

ϵϵ-regular vertex partitions, equitable partitions, and refinement

Definition

The mean-square density, or energy, of a vertex partition

Definition

Energy lies in [0,1][0,1] and cannot decrease under refinement

Statement

Facts & Assumptions

Proof

An irregularity witness raises the pair energy by more than ϵ4∣X∣∣Y∣/n2ϵ4∣X∣∣Y∣/n2

Statement

Facts & Assumptions

Proof

Every nonregular kk-part partition has a refinement with energy gain greater than ϵ5ϵ5 and at most k2k+1k2k+1 parts

Statement

Facts & Assumptions

Proof

Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least m0m0​

Statement

Facts & Assumptions

Proof

A prescribed finite vertex partition has a bounded ϵϵ-regular refinement, equitable when the initial partition is equitable

Statement

Facts & Assumptions

Proof

Every finite graph has a linearly large ϵϵ-self-regular vertex subset

Statement

Facts & Assumptions

Proof

Every finite graph has a bounded partition into self-regular vertex sets

Statement

Facts & Assumptions

Proof

Triangle counting lemma for three pairwise regular vertex sets

Statement

Facts & Assumptions

Proof

Counting lemma: regular dense pairs contain many part-respecting copies of every fixed graph

Statement

Facts & Assumptions

Proof

Induced counting lemma: regular edge and nonedge pairs force many induced copies

Statement

Facts & Assumptions

Proof

Graph edit distance and being ϵϵ-far from an induced-hereditary property

Definition

Graph removal lemma for a fixed ordinary subgraph

Statement

Facts & Assumptions

Proof

Equitable strong regularity lemma: a very regular refinement that changes energy only slightly

Statement

Facts & Assumptions

Proof

A small energy increment makes fine-pair densities close to their coarse densities almost everywhere

$ϵ$ -regular pairs and self-regular vertex sets

Complementation sends a disjoint $ϵ$ -regular pair of density $d$ to one of density $1 - d$

In a regular pair, fewer than $ϵ ∣ X ∣$ vertices have too small a degree into a large subset, and fewer than $ϵ ∣ X ∣$ have too large a degree

Slicing lemma: large subpairs remain regular and their density shifts by at most $ϵ$

$ϵ$ -regular vertex partitions, equitable partitions, and refinement

Energy lies in $[0, 1]$ and cannot decrease under refinement

An irregularity witness raises the pair energy by more than $ϵ^{4} ∣ X ∣ ∣ Y ∣ / n^{2}$

Every nonregular $k$ -part partition has a refinement with energy gain greater than $ϵ^{5}$ and at most $k 2^{k + 1}$ parts

Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_{0}$

A prescribed finite vertex partition has a bounded $ϵ$ -regular refinement, equitable when the initial partition is equitable

Every finite graph has a linearly large $ϵ$ -self-regular vertex subset

Graph edit distance and being $ϵ$ -far from an induced-hereditary property