Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-27
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.

Large sparse-pair hypotheses yield an x-sparse or complete blockade

Statement

Let x∈(0,12), let a>1, b>0, and let c:=2−4b. Let y∈(0,c]. Suppose that G is a graph with ∣G∣≥y−(a+2) such that for every induced subgraph F of G with ∣F∣≥c∣G∣, there are disjoint sets X,Y⊆V(F) satisfying

∣X∣≥ya∣F∣,∣Y∣≥(1−by)∣F∣,

and such that Y is x-sparse or complete to X.

Then G contains an x-sparse or complete (⌈y−1⌉,ya+2∣G∣)-blockade.

Facts & Assumptions

Given: The hypotheses of the statement.

Proof

technique · direct
1.1givenchoose

Let n be maximal such that G has a blockade (B1,…,Bn) with ∣Bi∣≥ya+2∣G∣ for all i, with ∣Bn∣≥(1−by)n∣G∣, and such that for every i∈[n], either every later block is x-sparse to Bi or every later block is complete to Bi. This is possible because n=1 and B1=V(G) already satisfy the conditions.

2.1step 1.1assume-contragivenalgebradischarge-contradiction

Suppose that n<2y−1. Since y≤c=2−4b, one has by≤b2−4b<1/2. For t∈[0,1/2] the elementary inequality 1−t≥2−2t holds, so with t=by we get (1−by)2y−1≥(2−2by)2y−1=2−4b=c. Therefore ∣Bn∣≥(1−by)n∣G∣≥c∣G∣. Applying the hypothesis to the induced subgraph G[Bn], choose disjoint X,Y⊆Bn with ∣X∣≥ya∣Bn∣≥ya+2∣G∣ and ∣Y∣≥(1−by)∣Bn∣≥(1−by)n+1∣G∣, and with Y x-sparse or complete to X. Because X∪Y⊆Bn, the relation of every earlier block Bi to Bn restricts to the same relation to both X and Y. Hence (B1,…,Bn−1,X,Y) is a larger blockade of the same type, contradicting the maximality of n. So n≥2y−1.

3.1step 1.1step 2.1algebra

Let Q be the set of indices i such that every later block is x-sparse to Bi, and let R be the set of indices i such that every later block is complete to Bi. By construction every index lies in Q∪R, so one of Q or R has cardinality at least n/2≥y−1.

4.1step 1.1step 3.1givenchoose

Since one of ∣Q∣,∣R∣ is an integer at least y−1, step 3.1 makes that cardinality at least ⌈y−1⌉. [step 3.1, given] If it is ∣Q∣, choose ⌈y−1⌉ indices from Q in their inherited order; the corresponding blocks form an x-sparse blockade. If it is ∣R∣, the same choice from R gives a complete blockade. Every selected block has size at least ya+2∣G∣ by step 1.1. Thus one of the two required blockades exists.

5.1step 4.1∎

Therefore G contains an x-sparse or complete (⌈y−1⌉,ya+2∣G∣)-blockade.

Depends on

Used by

Dependency tree · two levels

9 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