Alphabeta Math
LemmaStatement: AI-adaptedProof: 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.

A wonderful anticonnected complete-or-sparse blockade yields a restricted subgraph or a large anticomplete pair

Statement

Let F be a wonderful finite family, and let a≥6 be a witness for wonderfulness. Let y∈(0,12) and let G be a y-sparse F‾-free graph. Suppose that

B=(B1,…,Bℓ)

is a blockade in G such that:

  1. ℓ≥y−a;
  2. all blocks have the same size w;
  3. every block Bi is anticonnected;
  4. every distinct pair (Bi,Bj) is either complete or mutually ya-sparse;
  5. the support satisfies ∣V(B)∣≤y∣G∣.

Then one of the following holds:

  1. G has a y4-restricted induced subgraph with at least w vertices; or
  2. there exist disjoint sets X,Y⊆V(G) with ∣X∣=w, ∣Y∣≥(1−4y)∣G∣, and Y anticomplete to X.

Facts & Assumptions

Given: The wonderful family F, its witness exponent a, the parameter y, the y-sparse graph G, and the blockade B=(B1,…,Bℓ) satisfying hypotheses 1-5.

[L1]

The definition of wonderfulness applied to B yields either a y4-restricted induced subgraph of size at least w, or an index i∈[ℓ] such that at most y∣G∣ vertices in V(G)∖V(B) have between 1 and ∣Bi∣/2−1 neighbours in Bi (Wonderful finite graph families).

[L2]

A y-sparse graph has maximum degree at most y∣G∣ on its full vertex set (c-sparse, c-dense and c-restricted vertex sets).

[L3]

A pair is anticomplete exactly when it has no cross-edges (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

Proof

technique · apply wonderfulness and then count the outside vertices that still see a chosen block
1.1L1given

Apply [L1] to the blockade B. If it yields a y4-restricted induced subgraph on at least w vertices, then outcome 1 of the present lemma holds immediately.

2.1step 1.1L2algebra

We may therefore assume that [L1] yields an index i∈[ℓ] for which at most y∣G∣ vertices outside V(B) are mixed on Bi. Let M be that exceptional set of mixed outside vertices. Every outside vertex with a neighbour in Bi but not in M has at least ∣Bi∣/2 neighbours in Bi. Since every vertex of Bi has total degree at most y∣G∣ by [L2], the number of outside vertices with at least ∣Bi∣/2 neighbours in Bi is at most 2y∣G∣.

3.1givenstep 2.1L3algebra

Let Y be the set of vertices in V(G)∖V(B) that have no neighbours in Bi, and let X:=Bi. By step 2.1, ∣Y∣≥∣G∣−∣V(B)∣−∣M∣−2y∣G∣≥∣G∣−y∣G∣−y∣G∣−2y∣G∣=(1−4y)∣G∣. By construction there are no edges between X and Y, so [L3] gives that Y is anticomplete to X. Because all blocks have size w, we also have ∣X∣=∣Bi∣=w. Thus outcome 2 holds.

4.1step 1.1step 3.1∎

Steps 1.1 and 3.1 prove that one of the two stated outcomes must occur.

Depends on

Used by

Dependency tree · two levels

14 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