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 a6 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. ya;
  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)yG.

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,YV(G) with X=w, Y(14y)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 yG vertices in V(G)V(B) have between 1 and Bi/21 neighbours in Bi (Wonderful finite graph families).

[L2]

A y-sparse graph has maximum degree at most yG 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

Proof technique: apply wonderfulness and then count the outside vertices that still see a chosen block.

1.1

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.

L1given
2.1

We may therefore assume that [L1] yields an index i[] for which at most yG 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 yG by [L2], the number of outside vertices with at least Bi/2 neighbours in Bi is at most 2yG.

step 1.1L2algebra
3.1

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, YGV(B)M2yGGyGyG2yG=(14y)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.

givenstep 2.1L3algebra
4.1

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

step 1.1step 3.1

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