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.
For -free graphs Rödl's theorem holds with , by an explicit argument
Example
If is nonempty and -free and , then contains an -restricted set of size at least .
Facts & Assumptions
Given: A real and a nonempty -free graph on vertices.
The components of a -free graph are cliques: if some component contained two edges sharing a vertex without the third edge, it would contain an induced (-free and -free graphs under the induced-subgraph convention, Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices, The connected components of a graph partition its vertex set and are its maximal connected subgraphs).
A clique is -dense, and if every vertex of the whole graph has fewer than neighbours then is -sparse because (-sparse, -dense and -restricted vertex sets).
Verification
By [L1], every component of is a clique.
If some component has at least vertices, then that component is a clique and hence -dense by [L2], so it is an -restricted set of the required size.
Otherwise every component has fewer than vertices, so every vertex has fewer than neighbours. Therefore the whole vertex set is -sparse by [L2].
In either case has an -restricted set of size at least .
Depends on
- Rödl: for every $H$ and every $\epsilon\in(0,\tfrac12)$ there is $\delta>0$ such that every nonempty $H$-free graph has an $\epsilon$-restricted vertex set of size at least $\delta|V(G)|$
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- The connected components of a graph partition its vertex set and are its maximal connected subgraphs
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- Connected graphs and connected components defined by the existence of vertex paths
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
19 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.