$c$-sparse, $c$-dense and $c$-restricted 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
• Subgraphs, induced subgraphs and spanning subgraphs
• Graph isomorphisms, automorphisms and graph complements
• The cardinality $\lvert A\rvert$ of a finite set

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
• Rödl: for every H and every ε∈(0,1/2) there is δ>0 such that every nonempty H-free graph has an ε-restricted vertex set of size at least δ|V(G)| Corollary
• Rödl's theorem for a nonempty family of forbidden induced subgraphs 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 edge-density form of Rödl's theorem: every nonempty H-free graph has a linearly large set of self-density at most ε or at least 1-ε Corollary
• A star has tiny self-density, yet no restricted subset containing its centre has more than two vertices Counterexample
• A subset of a c-sparse set that is not c-sparse Counterexample
• The dense alternative in Rödl's theorem cannot be dropped Counterexample
• Sparsity of one vertex set to another, and weak sparsity of a pair Definition
• For 0≤ε<1/2, every sufficiently large ε-restricted set lies in one side Example
• For P₃-free graphs Rödl's theorem holds with δ=ε, by an explicit argument Example
• In a disjoint union of cliques of order k the whole vertex set is (k/n)-sparse Example
• The 0-sparse sets are exactly the stable sets and the 0-dense sets exactly the cliques Example
• The two sides of a balanced complete bipartite graph are large restricted sets Example
• Every c-sparse set of size m contains a stable set of size at least m/2 False statement
• 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 is c-sparse exactly when the maximum degree of the graph it induces is at most c times its size Lemma
• A set is c-sparse in G exactly when it is c-dense in Ḡ, so c-restrictedness is complement-invariant 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
• Sparsity is preserved when the parameter grows, and every nonempty set of at most two vertices is 0-restricted Lemma
• Bounded degree against bounded density: the two statements of Rödl's theorem, and which one is stronger Remark
• Why the self-density bound for a dense set carries a 1/|X| slack Remark
• 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

Dependency tree · two levels

12 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. 1.1 (standard reference, not scraped)