LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-09-01

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.

The auxiliary pattern then has a polynomial-size clique or stable set

Statement

Let $F$ be a finite family of finite graphs. Assume one of the following.

There exist $F_{⋆} \in F$ and an integer $t \geq 1$ such that $F_{⋆}$ is an induced subgraph of the $1$ -subdivision of $K_{1, t}$ .
There exist a graph $H$ on vertex set $[q]$ with $12 \in E (H)$ , with distinguished vertices $1, 2$ , such that ${H} \cup \overline{F}$ has the Erdős-Hajnal property and $H^{+}$ is not $\overline{F}$ -free. Let $m$ be the maximum order of a graph in ${H} \cup \overline{F}$ .

Then there exists $c \in (0, 1)$ , depending only on $t$ in condition 1 and only on ${H} \cup \overline{F}$ in condition 2, with the following property.

Let $a \in R$ , let $y \in (0, \frac{1}{2})$ , let $G$ be a $\overline{F}$ -free graph, and let $s$ be a positive integer. Let $B_{1}, \dots, B_{s} \subseteq V (G)$ and $v \in V (G) ∖ ⋃_{i = 1}^{s} B_{i}$ satisfy the hypotheses of Mixed anticonnected blocks lift pattern obstructions to the ambient graph with $η : = y^{a}$ , and let $J$ be the corresponding auxiliary graph on $[s]$ . In condition 2, assume also that $a \geq m$ .

Then $J$ has a clique or a stable set of size at least $∣ J ∣^{c}$ .

Facts & Assumptions

Given: The finite family $F$ , a chosen applicable obstruction condition, and arbitrary instance data $a, y, G, s, v, B_{1}, \dots, B_{s}, J$ satisfying the uniform assertion in the Statement.

[L1]

A clique of size $t$ in $J$ lifts to an induced copy of the complement of the $1$ -subdivision of $K_{1, t}$ in $G$ . After relabelling the indices of an induced copy of a graph $F$ of order $r$ as $[r]$ , that copy lifts block-by-block to an induced copy of $F$ in $G$ provided $(r - 1) η < 1$ . If the copied graph is $H$ with $12 \in E (H)$ , then it lifts together with $v$ to an induced copy of $H^{+}$ provided $(q - 1) η < \frac{1}{2}$ (Mixed anticonnected blocks lift pattern obstructions to the ambient graph).

[L2]

For every integer $t \geq 1$ , the class of $K_{t}$ -free graphs has the Erdős-Hajnal property (For every $t \geq 1$ , the class of $K_{t}$ -free graphs has the Erdős–Hajnal property).

[L3]

If a hereditary class has the Erdős-Hajnal property, then some $c > 0$ satisfies $hom (X) \geq ∣ V (X) ∣^{c}$ for every nonempty graph $X$ in that class (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

[L4]

The homogeneous number is the maximum of the clique number and the stable set number (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

Proof

technique · separate the star-subdivision and special-vertex cases

1.1

[assume-case star] Assume condition 1, with $F_{⋆}$ an induced subgraph of the $1$ -subdivision of $K_{1, t}$ . If $J$ had a clique of size $t$ , then [L1] would give an induced copy of the complement of that $1$ -subdivision in $G$ . Because complementation preserves induced-subgraph containment, $\overline{F_{⋆}}$ would then occur as an induced subgraph of $G$ . But $\overline{F_{⋆}} \in \overline{F}$ , contradicting that $G$ is $\overline{F}$ -free. So $J$ is $K_{t}$ -free.

L1givencontradiction: if $J$ had a $K_t$

1.2

[assume-case special] Assume condition 2, and write $G : = {H} \cup \overline{F}$ . By the Erdős-Hajnal property of $G$ , [L3] gives an Erdős-Hajnal constant $ϵ > 0$ for $G$ . Put $c : = \min {ϵ, \frac{1}{2}} \in (0, 1)$ . Then every nonempty $G$ -free graph $X$ satisfies $hom (X) \geq ∣ V (X) ∣^{c}$ .

L3givenalgebra

2.1

[assume-case star] By [L2] and [L3], the class of $K_{t}$ -free graphs has an Erdős-Hajnal constant $ϵ > 0$ . Put $c : = \min {ϵ, \frac{1}{2}} \in (0, 1)$ . Since $s \geq 1$ , the graph $J$ is nonempty, so applying the bound to the $K_{t}$ -free graph $J$ from step 1.1 and then using [L4], $J$ has a clique or a stable set of size at least $∣ J ∣^{c}$ .

step 1.1L2L3L4algebra

2.2

[assume-case special] We claim that $J$ is $G$ -free. If $J$ contained an induced copy of some $F \in \overline{F}$ with $r : = ∣ V (F) ∣$ , then $r \leq m \leq a$ , so $(r - 1) y^{a} \leq (r - 1) 2^{- a} \leq (r - 1) 2^{- r} < 1$ . Relabel the indices of that copy as $[r]$ ; [L1] then lifts it to an induced copy of $F$ in $G$ , contradicting that $G$ is $\overline{F}$ -free. If $J$ contained an induced copy of $H$ , relabel its indices as $[q]$ . Since $q \leq m \leq a$ gives $(q - 1) y^{a} < (q - 1) 2^{- a} \leq (q - 1) 2^{- q} < \frac{1}{2}$ , [L1] lifts it to an induced copy of $H^{+}$ in $G$ . Since $H^{+}$ is not $\overline{F}$ -free by hypothesis, that would again contradict the $\overline{F}$ -freeness of $G$ . Hence $J$ is $G$ -free.

step 1.2L1contradiction: if $J$ contained a forbidden pattern

3.1

[assume-case special] Since $s \geq 1$ , applying step 1.2 to the nonempty $G$ -free graph $J$ and then using [L4], we obtain a clique or a stable set in $J$ of size at least $∣ J ∣^{c}$ .

step 1.2step 2.2L4given

4.1

Steps 2.1 and 3.1 cover the two hypotheses in the Statement. In the star case, $c$ depends only on $t$ ; in the special case, it depends only on $G = {H} \cup \overline{F}$ . Thus the chosen $c$ is independent of $a, y, G, v$ , and the blocks, and $J$ has a clique or a stable set of size at least $∣ J ∣^{c}$ .

step 2.1step 3.1cases-exhaustive∎

Depends on

Used by

Star and special-vertex obstructions force wonderfulness Lemma

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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Claim 2.1.1 (standard reference, not scraped)