LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16

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.

Slicing lemma: large subpairs remain regular and their density shifts by at most $ϵ$

Statement

Let $(X, Y)$ be $ϵ$ -regular, and let $X^{'} \subseteq X$ , $Y^{'} \subseteq Y$ satisfy $∣ X^{'} ∣ \geq α ∣ X ∣$ and $∣ Y^{'} ∣ \geq β ∣ Y ∣$ , where $α, β \geq ϵ > 0$ . Then $∣ d (X^{'}, Y^{'}) - d (X, Y) ∣ \leq ϵ,$ and $(X^{'}, Y^{'})$ is $ϵ^{'}$ -regular for $ϵ^{'} = \max {ϵ / α, ϵ / β, 2 ϵ} .$

Facts & Assumptions

Given: The pair and subsets in the Statement.

[L1]

An $ϵ$ -regular pair has every subpair whose two sides meet the $ϵ$ relative-size thresholds within $ϵ$ of its density ( $ϵ$ -regular pairs and self-regular vertex sets).

Proof

technique · direct

1.1givenL1

Since $∣ X^{'} ∣ \geq ϵ ∣ X ∣$ and $∣ Y^{'} ∣ \geq ϵ ∣ Y ∣$ , [L1] gives $∣ d (X^{'}, Y^{'}) - d (X, Y) ∣ \leq ϵ$ .

1.2givenalgebra

Let $A \subseteq X^{'}$ and $B \subseteq Y^{'}$ satisfy $∣ A ∣ \geq ϵ^{'} ∣ X^{'} ∣$ and $∣ B ∣ \geq ϵ^{'} ∣ Y^{'} ∣$ . Then $∣ A ∣ \geq (ϵ / α) α ∣ X ∣ = ϵ ∣ X ∣$ and similarly $∣ B ∣ \geq ϵ ∣ Y ∣$ .

2.1step 1.1step 1.2L1algebra

By [L1], $∣ d (A, B) - d (X, Y) ∣ \leq ϵ$ ; combining this with step 1.1 yields $∣ d (A, B) - d (X^{'}, Y^{'}) ∣ \leq 2 ϵ \leq ϵ^{'}$ .

3.1step 2.1L1∎

Since $A, B$ were arbitrary at the $ϵ^{'}$ thresholds, $(X^{'}, Y^{'})$ is $ϵ^{'}$ -regular.

Depends on

$\epsilon$-regular pairs and self-regular vertex sets

Used by

Dependency tree · two levels

2 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

Y. Zhao, Graph Theory and Additive Combinatorics, Exercise 2.1.4 (standard reference, not scraped)

Slicing lemma: large subpairs remain regular and their density shifts by at most ϵϵ