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.
The induced-embedding count
Definition
For finite graphs and , define the induced-embedding count
The set inside the cardinality is a subset of the finite function set , so the displayed natural number is well defined (The set of functions between finite sets is finite, with , A subset of a finite set is finite, with , and equality holds if and only if , The cardinality of a finite set).
This convention counts labelled embeddings, not vertex subsets. An induced copy with image contributes one embedding for each isomorphism (Induced embeddings and induced copies of a graph).
Depends on
- Induced embeddings and induced copies of a graph
- The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $\lvert A^{B}\rvert = \lvert A\rvert^{\lvert B\rvert}$
- A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
- The cardinality $\lvert A\rvert$ of a finite set
Used by
- 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
- The viral property implies the polynomial Rödl property Corollary
- Induced removal must permit adding edges as well as deleting them Counterexample
- H-free and F-free graphs under the induced-subgraph convention Definition
- Induced copy density and homogeneous restriction parameter Definition
- The viral property for a finite forbidden family Definition
- A family containing K₁ is viral for vacuous reasons 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
- Ell divisibility amplifies through a blockade Lemma
- If G has fewer than (δ n)ʰ induced copies of H and |W|≥λ n, then G[W] has fewer than ((δ/λ)|W|)ʰ Lemma
- ind_H(G) is isomorphism-invariant and equals ind_H̄(Ḡ) Lemma
- Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph Lemma
- Small total induced-copy expectation forces many homogeneous k-sets 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
- Every finite family with the Erdős–Hajnal property is viral Theorem
- Induced counting lemma: regular edge and nonedge pairs force many induced copies Theorem
- Induced graph removal lemma for a fixed graph 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
23 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
- Swastik Kopparty, Local Structure: Subgraph Counts I (standard reference, not scraped)