LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-04

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.

Iterated restricted sparsification reaches the target scale

Statement

Let $c \in (0, 1)$ , let $b_{1} > 1$ , let $b_{2}, b_{3} > 0$ , and assume

$b_{1} b_{2} \geq b_{2} + b_{3} .$

Suppose that $x \in (0, c)$ and that a graph $G$ satisfies:

$G$ has a $c$ -restricted induced subgraph with at least $c^{b_{2}} ∣ G ∣$ vertices; and
for every $λ \in [x, c]$ and every $λ$ -restricted induced subgraph $F$ of $G$ with $∣ F ∣ \geq λ^{b_{2}} ∣ G ∣$ , there is a $λ^{b_{1}}$ -restricted induced subgraph of $F$ with at least $λ^{b_{3}} ∣ F ∣$ vertices.

Then $G$ contains an $x$ -restricted induced subgraph with at least $x^{b_{1} b_{2}} ∣ G ∣$ vertices.

Facts & Assumptions

Given: The parameters $c, b_{1}, b_{2}, b_{3}, x$ and the two hypotheses in the statement.

[L1]

A set is $λ$ -restricted exactly when it is $λ$ -sparse or $λ$ -dense in the induced subgraph on that set ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

Proof

technique · minimal admissible restriction parameter

1.1

By hypothesis 1, there exists at least one induced subgraph of $G$ that is $c$ -restricted and has at least $c^{b_{2}} ∣ G ∣$ vertices. Therefore the set of admissible restriction parameters considered below is nonempty.

givenL1

2.1

For a nonempty induced subgraph $E$ of $G$ , let $ρ (E)$ be the smallest real number $λ \in [0, 1]$ such that $E$ is $λ$ -restricted. Because $E$ is finite, [L1] shows that $ρ (E)$ is attained by one of finitely many degree or codegree ratios in $E$ . Choose an induced subgraph $F$ of $G$ for which $λ : = \max (x^{b_{1}}, ρ (F))$ is minimal subject to $∣ F ∣ \geq λ^{b_{2}} ∣ G ∣$ . Step 1.1 ensures that such a choice exists and that $λ \leq c$ .

step 1.1L1choose

3.1

Suppose $λ \geq x$ . Then $λ = ρ (F)$ , so hypothesis 2 applies to $F$ and yields a $λ^{b_{1}}$ -restricted induced subgraph $F^{'} \subseteq F$ with $∣ F^{'} ∣ \geq λ^{b_{3}} ∣ F ∣ \geq λ^{b_{2} + b_{3}} ∣ G ∣ \geq λ^{b_{1} b_{2}} ∣ G ∣$ , where the last inequality uses $b_{1} b_{2} \geq b_{2} + b_{3}$ . Because $F^{'}$ is $λ^{b_{1}}$ -restricted, its admissible parameter satisfies $\max (x^{b_{1}}, ρ (F^{'})) \leq λ^{b_{1}} < λ$ , while $∣ F^{'} ∣ \geq \max (x^{b_{1}}, ρ (F^{'}))^{b_{2}} ∣ G ∣$ . This contradicts the minimal choice of $λ$ in step 2.1. Hence $λ < x$ .

step 2.1givenassume-contraalgebradischarge-contradiction

4.1

Since $λ = \max (x^{b_{1}}, ρ (F))$ , step 2.1 gives $x^{b_{1}} \leq λ < x$ by step 3.1. Therefore $ρ (F) \leq λ < x$ , so $F$ is $x$ -restricted. Its size also satisfies $∣ F ∣ \geq λ^{b_{2}} ∣ G ∣ \geq (x^{b_{1}})^{b_{2}} ∣ G ∣ = x^{b_{1} b_{2}} ∣ G ∣$ .

step 2.1step 3.1algebra

5.1

The induced subgraph $F$ from step 4.1 is the required $x$ -restricted induced subgraph.

step 4.1∎

Depends on

$c$-sparse, $c$-dense and $c$-restricted vertex sets

Used by

Dependency tree · two levels

6 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

Tung H. Nguyen, Notes on Recent Work on the Erdos-Hajnal Conjecture, Lemma 5.3 (standard reference, not scraped)