Alphabeta Math

Regular Pairs and Induced Counting

About this page
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.
1 · Prerequisites
Abstract Algebra
Combinatorics
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

Edge counts and densities between nonempty vertex sets

Definition

ε-regular pairs and self-regular vertex sets

Lemma

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

Lemma

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

Lemma

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

Lemma

Regularity survives sufficiently small changes of vertices and cross-edges

Definition

ε-regular vertex partitions, equitable partitions, and refinement

Definition

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

Lemma

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

Lemma

An irregularity witness raises the pair energy by more than ε⁴|X||Y|/n²

Lemma

Every nonregular k-part partition has a refinement with energy gain greater than ε⁵ and at most k2ᵏ⁺¹ parts

Theorem

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

Corollary

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

Theorem

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

Corollary

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

Theorem

Triangle counting lemma for three pairwise regular vertex sets

Theorem

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

Theorem

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

Definition

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

Theorem

Graph removal lemma for a fixed ordinary subgraph

Theorem

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

Lemma

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

Theorem

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

Remark

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

Theorem

Induced graph removal lemma for a fixed graph

Sources