LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-26

How 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.

If every $m$ -element vertex set contains an induced copy of $H$ , then at least $(\binom{n}{h}) / (\binom{m}{h})$ of the $h$ -element vertex sets induce a copy of $H$

Statement

Let $H$ be a finite simple graph with $h = ∣ V (H) ∣ \geq 1$ , let $G$ be a finite simple graph with $n = ∣ V (G) ∣$ , and let $m$ be a natural number with $h \leq m \leq n$ . Suppose every $W \subseteq V (G)$ with $∣ W ∣ = m$ has a subset $S \subseteq W$ with $∣ S ∣ = h$ and $G [S] ≅ H$ . Let $g$ be the number of sets $S \subseteq V (G)$ with $∣ S ∣ = h$ and $G [S] ≅ H$ . Then

$g \geq \frac{(\binom{n}{h})}{(\binom{m}{h})} \geq \frac{(n - h + 1)^{h}}{m^{h}} .$

Facts & Assumptions

Given: Finite simple graphs $H$ and $G$ with $h = ∣ V (H) ∣ \geq 1$ and $n = ∣ V (G) ∣$ , a natural number $m$ with $h \leq m \leq n$ , and the hypothesis that every $m$ -element $W \subseteq V (G)$ has an $h$ -element subset $S$ with $G [S] ≅ H$ .

[F1]

For a finite set $A$ and $k \in N$ , $[A]^{k}$ is the set of $k$ -element subsets of $A$ , it is finite, and $∣ [A]^{k} ∣ = (\binom{∣ A ∣}{k})$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , The cardinality $∣ A ∣$ of a finite set).

[L1]

For finite sets $X, Y$ and a relation $R \subseteq X \times Y$ with row fibres $R_{x}$ and column fibres $R^{y}$ , one has $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets, A relation $R \subseteq X \times Y$ between finite sets, its row fibres $R_{x}$ and its column fibres $R^{y}$ ).

[F2]

For a finite index set $S$ and a constant $c$ , $\sum_{i \in S} c = ∣ S ∣ \cdot c$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

[L2]

Every subset of a finite set is finite, and its cardinality is at most that of the set (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L3]

For $k \leq N$ one has $(\binom{N}{k}) \cdot k! = N^{\underline{k}}$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[F3]

$N^{\underline{0}} = 1$ and $N^{\underline{k + 1}} = N^{\underline{k}} \cdot (N - k)$ , so for $k \leq N$ the falling factorial $N^{\underline{k}}$ is the product $N (N - 1) \dots (N - k + 1)$ of the $k$ topmost factors (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[F4]

An induced copy of $H$ in $G$ is the image $G [φ (V (H))]$ of an induced embedding, and $G [S] = (S, E (G) \cap [S]^{2})$ (Induced embeddings and induced copies of a graph, Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · direct

1.1F1F4L2

Write $G = {S \in [V (G)]^{h} : G [S] ≅ H}$ , so $g = ∣ G ∣$ , and let $R \subseteq [V (G)]^{m} \times [V (G)]^{h}$ consist of the pairs $(W, S)$ with $S \subseteq W$ , and $R^{'} \subseteq R$ of those with $S \in G$ . Both index sets are finite.

1.2F1L2

The row fibre of $R$ at $W$ is $[W]^{h}$ , of size $(\binom{m}{h})$ , and the column fibre of $R$ at $S$ is ${W \in [V (G)]^{m} : S \subseteq W}$ , which the map $W \mapsto W ∖ S$ carries bijectively onto $[V (G) ∖ S]^{m - h}$ , of size $(\binom{n - h}{m - h})$ .

1.3F1givenL2

The row fibre of $R^{'}$ at $W$ is ${S \in G : S \subseteq W}$ , which is nonempty by hypothesis, and the column fibre of $R^{'}$ at $S \in G$ is the same set as for $R$ , of size $(\binom{n - h}{m - h})$ , while the column fibre at $S \notin G$ is empty.

1.4L3F3algebra

By [L3] and [F3], $(\binom{n}{h}) h! = n^{\underline{h}} = n (n - 1) \dots (n - h + 1)$ and $(\binom{m}{h}) h! = m^{\underline{h}} = m (m - 1) \dots (m - h + 1)$ , so $(\binom{n}{h}) / (\binom{m}{h}) = n^{\underline{h}} / m^{\underline{h}}$ .

2.1step 1.1step 1.2L1F1F2

Double counting $R$ with the two fibre sizes of step 1.2 and the constant-summand rule gives $(\binom{n}{m}) (\binom{m}{h}) = ∣ R ∣ = (\binom{n}{h}) (\binom{n - h}{m - h})$ .

2.2step 1.1step 1.3L1F1F2algebra

Double counting $R^{'}$ gives $∣ R^{'} ∣ = \sum_{W} ∣ R_{W}^{'} ∣ \geq \sum_{W} 1 = (\binom{n}{m})$ , since every row fibre has at least one element, and also $∣ R^{'} ∣ = g (\binom{n - h}{m - h})$ by summing the column fibres of step 1.3 over $G$ .

2.3step 1.4F3algebra

Each of the $h$ factors of $n^{\underline{h}}$ is at least $n - h + 1 \geq 1$ and each of the $h$ factors of $m^{\underline{h}}$ is at most $m$ , and all of them are positive because $h \leq m \leq n$ ; hence $n^{\underline{h}} \geq (n - h + 1)^{h}$ and $m^{\underline{h}} \leq m^{h}$ , so $n^{\underline{h}} / m^{\underline{h}} \geq (n - h + 1)^{h} / m^{h}$ .

3.1step 2.1step 2.2F1algebra

Since $m - h \leq n - h$ and $h \leq m$ , the sets $[n - h]^{m - h}$ and $[m]^{h}$ are nonempty, so $(\binom{n - h}{m - h}) \geq 1$ and $(\binom{m}{h}) \geq 1$ ; dividing the inequality of step 2.2 by $(\binom{n - h}{m - h})$ and substituting step 2.1 gives $g \geq (\binom{n}{m}) / (\binom{n - h}{m - h}) = (\binom{n}{h}) / (\binom{m}{h})$ .

4.1step 3.1step 1.4step 2.3algebra∎

Combining steps 3.1, 1.4 and 2.3 gives $g \geq (\binom{n}{h}) / (\binom{m}{h}) \geq (n - h + 1)^{h} / m^{h}$ .

Depends on

Used by

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

Dependency tree · two levels

46 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

M. Chudnovsky, The Erdős–Hajnal Conjecture: A Survey, sec. 2 (standard reference, not scraped)

If every mm-element vertex set contains an induced copy of HH, then at least (nh)/(mh)(hn​)/(hm​) of the hh-element vertex sets induce a copy of HH