Alphabeta Math
CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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.

Large almost-pure pair hypotheses yield a complete or anticomplete blockade

Statement

Let a>1, b>0, put c:=2−4b, and assume y∈(0,min⁡{12,c}]. Assume that ∣G∣≥y−(a+2). Suppose that every induced subgraph F of G with ∣F∣≥c∣G∣ contains disjoint sets X,Y⊆V(F) such that

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

and Y is complete or anticomplete to X. Then G contains a complete or anticomplete (⌈y−1⌉,ya+2∣G∣)-blockade.

Facts & Assumptions

Given: The parameters a,b,y, the graph G, and the large almost-pure pair hypothesis on every induced subgraph of size at least c∣G∣.

[L1]

A pair is pure exactly when it is complete or anticomplete (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

[L2]

A blockade is an ordered sequence of pairwise disjoint nonempty vertex sets, and its width is the minimum block size (Blockades, their length, their width, and their support).

Proof

technique · maximal blockade extension
1.1givenchooseL2algebra

Let n be maximal such that G has a blockade (B1,…,Bn) with ∣Bi∣≥ya+2∣G∣ for all i∈[n], with ∣Bn∣≥(1−by)n∣G∣, and with the property that for each i∈[n], either every later block is complete to Bi, or every later block is anticomplete to Bi. This is possible because 0<ya+2≤1, so B1:=V(G) already satisfies the required lower bounds.

2.1step 1.1L1assume-contrachoosealgebradischarge-contradiction

Suppose n<2y−1. The bound y≤c=2−4b implies by<12, and the elementary inequality 1−t≥2−2t for t∈[0,12] gives (1−by)n≥(1−by)2y−1≥2−4b=c. Hence ∣Bn∣≥c∣G∣, so the hypothesis applies to G[Bn]. Choose disjoint X,Y⊆Bn with ∣X∣≥ya∣Bn∣≥yac∣G∣≥ya+2∣G∣, where the last inequality uses c≥y≥y2, and with ∣Y∣≥(1−by)∣Bn∣≥(1−by)n+1∣G∣, and Y complete or anticomplete to X. Moreover, ∣Y∣≥(1−by)c∣G∣>12c∣G∣≥12y∣G∣≥ya+2∣G∣, where the last inequality follows from a>1 and y≤12. Because X∪Y⊆Bn, every earlier block has the same pure relation to both X and Y that it had to Bn. Thus (B1,…,Bn−1,X,Y) is a longer 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 complete to Bi, and let R be the set of indices i such that every later block is anticomplete to Bi. By construction every index lies in Q∪R, so one of Q or R has size at least n/2≥y−1.

4.1step 1.1step 3.1choosealgebra

If ∣Q∣≥y−1, choose ⌈y−1⌉ indices from Q in their inherited order. The corresponding blocks form a complete blockade, and every block has size at least ya+2∣G∣ by step 1.1. If instead ∣R∣≥y−1, the same construction with R gives an anticomplete blockade. In either case we obtain a complete or anticomplete (⌈y−1⌉,ya+2∣G∣)-blockade.

5.1step 4.1∎

Therefore the stated blockade exists.

Depends on

Used by

Dependency tree · two levels

4 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