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.
A set is -sparse exactly when the maximum degree of the graph it induces is at most times its size
Statement
Let be a finite simple graph, let , and let be nonempty. Then is -sparse in if and only if every vertex of the induced subgraph has degree at most . In particular, if , then is -sparse in if and only if it is -sparse in .
Facts & Assumptions
Given: A finite simple graph , a real , and a nonempty set .
The set is -sparse when for every (-sparse, -dense and -restricted vertex sets).
In the induced subgraph , the neighbours of a vertex are exactly the vertices of (Subgraphs, induced subgraphs and spanning subgraphs, Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).
Proof
By [L2], for each the degree of in is exactly .
Therefore the inequalities in [L1] are exactly the degree bounds in the induced subgraph.
The same identity of neighbourhoods holds in any larger induced subgraph containing , so the ambient graph is irrelevant once the vertex set is fixed.
Depends on
Used by
- A c-sparse set X satisfies α(G[X])≥|X|/(c|X|+1), and a c-dense set satisfies ω(G[X])≥|X|/(c|X|+1) Corollary
- A linearly large induced subgraph of a graph with few induced copies again has a linearly large restricted set Corollary
- For every λ>0 a bounded number of disjoint ε-restricted sets covers all but λ|V(G)| vertices of an H-free graph Corollary
- The polynomial Rödl property implies the Erdős–Hajnal property Corollary
- A c-sparse set has self-density at most c, and a c-dense set has self-density at least 1-c-1/|X| Lemma
- A set of self-density at most c has a subset of at least half its size that is 4c-sparse Lemma
- A subset occupying at least a λ fraction of a c-sparse set is (c/λ)-sparse 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
- Without a large ε-sparse induced subgraph, the number of k-vertex stable sets is bounded Lemma
- Every finite family with the Erdős–Hajnal property is viral Theorem
- Every H-free graph has a homogeneous set of size at least 2^c√log₂ n Theorem
- Every H-free graph has a homogeneous set of size at least 2^c√log₂ n log₂ log₂ n Theorem
Dependency tree · two levels
6 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
- M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, Strengthening Rödl's theorem, sec. 1 (standard reference, not scraped)