Alphabeta MathHow 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.
-regular pairs and self-regular vertex sets
Definition
Let be nonempty vertex sets in a graph and let . The pair is -regular if every and with and satisfies If this fails, such are an irregularity witness. The definition permits and permits overlap. A nonempty vertex set is -self-regular when is -regular (Edge counts and densities between nonempty vertex sets).
We also call a pair -regular when every pair of nonempty subsets , has . This is the exact limiting form of the positive-parameter definition and avoids assigning a density to an empty subpair.
Depends on
Used by
- A prescribed finite vertex partition has a bounded ε-regular refinement, equitable when the initial partition is equitable Corollary
- The half graph has no regularity across its natural bipartition at a fixed small parameter Counterexample
- ε-regular vertex partitions, equitable partitions, and refinement Definition
- Complete and anticomplete disjoint pairs are 0-regular Example
- The triangle counting lemma is exact for three complete cross-pairs Example
- Two complete pairs and one anticomplete pair produce exactly |X₁||X₂||X₃| induced copies of P₃ Example
- An irregularity witness raises the pair energy by more than ε⁴|X||Y|/n² 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
- Regularity survives sufficiently small changes of vertices and cross-edges Lemma
- Slicing lemma: large subpairs remain regular and their density shifts by at most ε Lemma
- Equitable strong regularity lemma: a very regular refinement that changes energy only slightly Theorem
- Every finite graph has a linearly large ε-self-regular vertex subset Theorem
- Triangle counting lemma for three pairwise regular vertex sets Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 5 results over 5 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Y. Zhao, Graph Theory and Additive Combinatorics, Definition 2.1.2 (standard reference, not scraped)
- D. Conlon and J. Fox, Graph removal lemmas, sec. 2.1 (standard reference, not scraped)