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:=24b, and assume y(0,min{12,c}]. Assume that Gy(a+2). Suppose that every induced subgraph F of G with FcG contains disjoint sets X,YV(F) such that

XyaF,Y(1by)F,

and Y is complete or anticomplete to X. Then G contains a complete or anticomplete (y1,ya+2G)-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 cG.

[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.1

Let n be maximal such that G has a blockade (B1,,Bn) with Biya+2G for all i[n], with Bn(1by)nG, 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+21, so B1:=V(G) already satisfies the required lower bounds.

givenchooseL2algebra
2.1

Suppose n<2y1. The bound yc=24b implies by<12, and the elementary inequality 1t22t for t[0,12] gives (1by)n(1by)2y124b=c. Hence BncG, so the hypothesis applies to G[Bn]. Choose disjoint X,YBn with XyaBnyacGya+2G, where the last inequality uses cyy2, and with Y(1by)Bn(1by)n+1G, and Y complete or anticomplete to X. Moreover, Y(1by)cG>12cG12yGya+2G, where the last inequality follows from a>1 and y12. Because XYBn, every earlier block has the same pure relation to both X and Y that it had to Bn. Thus (B1,,Bn1,X,Y) is a longer blockade of the same type, contradicting the maximality of n. So n2y1.

step 1.1L1assume-contrachoosealgebradischarge-contradiction
3.1

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 QR, so one of Q or R has size at least n/2y1.

step 1.1step 2.1algebra
4.1

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

step 1.1step 3.1choosealgebra
5.1

Therefore the stated blockade exists.

step 4.1

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