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
- A large γ-self-regular set whose density lies between η and 1-η forces at least c|W|^|V(H)| induced copies of H Lemma
- An irregularity witness raises the pair energy by more than ε⁴|X||Y|/n² Lemma
- An ε-regular pair is ε'-regular for every ε'≥ε with ε'>0 Lemma
- Complementation sends a disjoint ε-regular pair of density d to one of density 1-d Lemma
- Deleting the high-degree vertices of a γ-self-regular set of density d leaves more than (1-γ) of it, and that remainder is ((d+γ)/(1-γ))-sparse Lemma
- Deleting the low-degree vertices of a γ-self-regular set of density d leaves more than (1-γ) of it, and that remainder is ((1-d+2γ)/(1-γ))-dense 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
- Nikiforov: for every H and every ε∈(0,1/2) there is δ>0 such that every graph G with ind_H(G)<(δ|V(G)|)^|V(H)| has an ε-restricted vertex set of size at least δ|V(G)| Theorem
- Triangle counting lemma for three pairwise regular vertex sets Theorem
Dependency tree · two levels
3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on 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)