LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

Many good $2 t$ -vertex subsets force many homogeneous $k$ -sets

Statement

Let $1 \leq k \leq t$ be integers, and let $C$ be a class of finite graphs such that every graph in $C$ has the $(t, k)$ -homogeneous property. Let $G$ be a finite graph on $n \geq 2 t$ vertices. Suppose at least half of the sets $X \in [V (G)]^{2 t}$ contain a $t$ -element subset $T \subseteq X$ with $G [T] \in C$ . Then $G$ has at least

$\frac{1}{2} {(\frac{n}{2 t})}^{k}$

homogeneous vertex sets of size $k$ .

Facts & Assumptions

Given: Positive integers $1 \leq k \leq t$ , a class $C$ of finite graphs, integers $n \geq 2 t$ , an $n$ -vertex graph $G$ , and the hypothesis that at least half of the sets $X \in [V (G)]^{2 t}$ contain a $t$ -element subset $T$ with $G [T] \in C$ .

[L1]

If a graph lies in $C$ , then every $t$ -element subset of its vertex set contains a homogeneous $k$ -element subset (The $(t, k)$ -homogeneous property, Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[L2]

For a subset $T \subseteq V (G)$ , the induced subgraph on $T$ is $G [T]$ (Subgraphs, induced subgraphs and spanning subgraphs).

[L3]

$(\binom{a}{b})$ counts the $b$ -element subsets of an $a$ -element set (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L4]

A finite relation can be counted by summing its row fibres or its column fibres (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets).

Proof

technique · direct

1.1givenL3

Call a set $X \in [V (G)]^{2 t}$ good when it contains a $t$ -element subset $T$ with $G [T] \in C$ ; by hypothesis, there are at least $\frac{1}{2} (\binom{n}{2 t})$ good sets.

1.2L1L2choose

If $X$ is good, choose $T \subseteq X$ with $∣ T ∣ = t$ and $G [T] \in C$ ; then [L1] gives a homogeneous $k$ -element subset $K \subseteq T$ , and since $G [T]$ is the induced subgraph on $T$ , that same set $K$ is homogeneous in $G$ .

2.1step 1.1step 1.2L4

Let $R$ be the relation between the homogeneous $k$ -element subsets $K$ of $V (G)$ and the good sets $X \in [V (G)]^{2 t}$ defined by $K \subseteq X$ . Step 1.2 shows that every good $X$ is related to at least one $K$ , so [L4] gives $∣ R ∣ \geq \frac{1}{2} (\binom{n}{2 t})$ .

3.1step 2.1L3L4

For the relation $R$ of step 2.1, fix a homogeneous $k$ -element subset $K$ of $V (G)$ . The good sets $X$ with $K \subseteq X$ are among the $2 t$ -element supersets of $K$ , and [L3] counts those as $(\binom{n - k}{2 t - k})$ . If $N$ is the number of homogeneous $k$ -element subsets of $V (G)$ , then [L4] gives $∣ R ∣ \leq N (\binom{n - k}{2 t - k})$ .

4.1step 2.1step 3.1algebra

Comparing steps 2.1 and 3.1 yields $N \geq \frac{1}{2} (\binom{n}{2 t}) / (\binom{n - k}{2 t - k}) = \frac{1}{2} (\binom{n}{k}) / (\binom{2 t}{k})$ .

5.1step 4.1algebra∎

Since $n \geq 2 t$ , each factor in the ratio formula satisfies $(n - j) / (2 t - j) \geq n / (2 t)$ for $0 \leq j < k$ , so $(\binom{n}{k}) / (\binom{2 t}{k}) \geq (n / (2 t))^{k}$ . Therefore $N \geq \frac{1}{2} (n / (2 t))^{k}$ .

Depends on

Used by

Dependency tree · two levels

19 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. Bucić, J. Fox, and H. T. Pham, Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures, Lemma 13 (standard reference, not scraped)
T. H. Nguyen, Notes on Recent Work on the Erdős–Hajnal Conjecture, Lemma 13 (standard reference, not scraped)

Many good 2t2t-vertex subsets force many homogeneous kk-sets