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.
Sparsity of one vertex set to another, and weak sparsity of a pair
Definition
Let be a finite simple graph and let .
- For disjoint nonempty sets , is -sparse to when every has at most neighbours in .
- For nonempty sets , the ordered pair is weakly -sparse when , with the ordered edge count of Edge counts and densities between nonempty vertex sets.
- Such a pair is weakly -dense when it is weakly -sparse in the complement graph.
The directional notion need not be symmetric, while the weak notion is an edge-count and so is symmetric. For nonempty , taking makes weak sparsity the self-density condition discussed in Edge counts and densities between nonempty vertex sets.
Depends on
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
- Edge counts and densities between nonempty vertex sets
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
Used by
- X can be c-sparse to Y while Y is not c-sparse to X Counterexample
- A set of self-density at most c has a subset of at least half its size that is 4c-sparse Lemma
- For disjoint nonempty vertex sets, weak c-sparsity says exactly that the edge density is at most c Lemma
- Bounded degree against bounded density: the two statements of Rödl's theorem, and which one is stronger Remark
Dependency tree · two levels
8 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. Huang, Q. Ju, and X. Zhou, Erdős-Hajnal beyond the five-vertex path, sec. 2 (standard reference, not scraped)