Induced embeddings and induced copies of a graph

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
• Subgraphs, induced subgraphs and spanning subgraphs
• Graph isomorphisms, automorphisms and graph complements
• Injection, surjection, bijection

Used by

• Few induced copies force a linearly large induced subgraph with bounded maximum degree Corollary
• K₃ contains P₃ as a subgraph but not as an induced subgraph Counterexample
• A blockade-rainbow induced copy Definition
• H-free and F-free graphs under the induced-subgraph convention Definition
• Hereditary graph classes Definition
• Induced copy density and homogeneous restriction parameter Definition
• Minimal forbidden induced subgraphs and forbidden bases Definition
• The induced-embedding count ind_H(G) Definition
• A graph is P₃-free if and only if every connected component is complete Example
• Counting the induced copies of P₃ in P₄ by extension sets Example
• ind_K₂(G)=2|E(G)| under the induced-embedding convention Example
• A large γ-self-regular set whose density lies between η and 1-η forces at least c|W|^|V(H)| induced copies of H Lemma
• A rooted stable-tooth comb with a cross-edge between two blocks contains an induced five-cycle Lemma
• An induced copy of H₂ inside the extension set of an induced embedding of H₁-v yields an induced copy of H₁ with H₂ substituted for v Lemma
• If every m-element vertex set contains an induced copy of H, then at least C(n, h)/C(m, h) of the h-element vertex sets induce a copy of H Lemma
• If G has fewer than (δ n)ʰ induced copies of H and |W|≥λ n, then G[W] has fewer than ((δ/λ)|W|)ʰ Lemma
• If ε is an Erdős–Hajnal constant for H and W is a nonempty vertex set with |W|^ε>hom(G), then G[W] has an induced copy of H Lemma
• In G₁ with G₂ substituted for a, the vertex set of G₂ is a module, the two factors are recovered as induced subgraphs, and substituting a one-vertex graph changes nothing Lemma
• ind_H(G) is isomorphism-invariant and equals ind_H̄(Ḡ) Lemma
• Induced embeddings compose, and the induced-subgraph relation is transitive up to isomorphism Lemma
• Relative to a complete nonedge pair in a co-E-free graph, a one-sided vertex mixed on an induced path avoids two consecutive nonneighbours and three consecutive neighbours Lemma
• The induced copies of H₁ in G are counted by summing, over the induced embeddings of H₁-v, the number of vertices that extend them at v Lemma
• Alon–Pach–Solymosi: if H₁ and H₂ have the Erdős–Hajnal property, so does the graph obtained from H₁ by substituting H₂ for a vertex Theorem
• Induced counting lemma: regular edge and nonedge pairs force many induced copies 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

• Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)