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
• Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs

Used by

• An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree Corollary
• Few induced copies force a linearly large induced subgraph with bounded maximum degree 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
• Three pair densities equal to 1/2 need not produce a single transversal triangle Counterexample
• Induced copy density and homogeneous restriction parameter Definition
• Sparsity of one vertex set to another, and weak sparsity of a pair Definition
• The mean-square density, or energy, of a vertex partition Definition
• ε-regular pairs and self-regular vertex sets Definition
• A clique of size s has self-density 1-1/s Example
• The triangle counting lemma is exact for three complete cross-pairs Example
• Two complete pairs and one anticomplete pair produce exactly |X₁||X₂||X₃| induced copies of P₃ Example
• 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 large γ-self-regular set whose density lies between η and 1-η forces at least c|W|^|V(H)| induced copies of H Lemma
• A set of self-density at most c has a subset of at least half its size that is 4c-sparse Lemma
• An ε-regular pair is ε'-regular for every ε'≥ε with ε'>0 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
• 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
• Why the self-density bound for a dense set carries a 1/|X| slack Remark
• 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
• Every H-free graph partitions into boundedly many vertex sets of self-density at most ε or at least 1-ε Theorem
• 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

4 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. Zhao, Graph Theory and Additive Combinatorics, Definition 2.1.1 (standard reference, not scraped)
• D. Conlon and J. Fox, Graph removal lemmas, sec. 2.1 (standard reference, not scraped)