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 in exactly when it is -dense in , so -restrictedness is complement-invariant
Statement
Let be a finite simple graph, let , and let be nonempty. Then is -sparse in if and only if is -dense in . Consequently is -restricted in if and only if it is -restricted in .
Facts & Assumptions
Given: A finite simple graph , a real , and a nonempty set .
For distinct vertices , they are adjacent in exactly when they are nonadjacent in (Graph isomorphisms, automorphisms and graph complements, Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).
The definitions of -sparse, -dense, and -restricted are those of -sparse, -dense and -restricted vertex sets.
Proof
For , the set is exactly by [L1].
Therefore the inequality defining -sparsity in is exactly the inequality defining -density in , and vice versa, by [L2].
Since -restricted means the disjunction of the sparse and dense conditions, step 2.1 shows that restrictedness is unchanged by complementation.
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
- The edge-density form of Rödl's theorem implies the maximum-degree form, with ε and δ each shrunk by a constant factor Corollary
- The polynomial Rödl property implies the Erdős–Hajnal property Corollary
- A large epsilon-restricted induced subgraph gives a polynomial clique or stable set Example
- The 0-sparse sets are exactly the stable sets and the 0-dense sets exactly the cliques Example
- An iterative sparsification step for sparse P₅-free graphs Lemma
- Generalized niceness yields four reduction outcomes Lemma
- Large induced subgraphs without a polynomial clique or stable set force complete or anticomplete blockades Lemma
- Property (*) and leaf reducibility yield five comb outcomes in a restricted graph Lemma
- Every finite family with the Erdős–Hajnal property is viral Theorem
- Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property Theorem
Dependency tree · two levels
7 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)