Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

Generalized niceness yields four reduction outcomes

Statement

Let F be a generalized nice, leaf-reducible, wonderful finite family of graphs. Then there exist constants a1,a2,a5>0 and a3a44 such that for every y(0,12) and every y-restricted F-free graph G, at least one of the following holds:

  1. G has a clique or stable set of size at least (ya1G)a2;
  2. G has a ya4-restricted induced subgraph with at least ya3G vertices;
  3. G has a complete or anticomplete (k,G/ka3)-blockade with ky1; or
  4. there exist disjoint sets X,YV(G) with Xya3G,Y(1a5y)G, and Y complete or anticomplete to X.

Facts & Assumptions

Given: A generalized nice, leaf-reducible, wonderful finite family F, a parameter y(0,12), and a y-restricted F-free graph G.

[L1]

Generalized niceness supplies constants c13, c28, c3,c4,c5,c8>0, c61, and c74 with the four alternatives in Generalized nice finite graph families.

[L2]

Leaf-reducibility supplies constants d>0 and h1 such that every y-sparse F-free graph yields either a large anticomplete pair or a deeper restricted induced subgraph (Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph).

[L4]

Wonderfulness supplies an exponent a6 as in Wonderful finite graph families.

[L5]

A complete-or-weakly-sparse blockade can be thinned to equal-sized subblocks with directional sparsity (A complete-or-weakly-sparse blockade can be thinned to equal subblocks with directional sparsity).

[L6]

Such an equal-sized blockade either contains a complete subblockade or can be thinned further to anticonnected subblocks (A complete-or-weakly-sparse blockade yields a complete subblockade or an anticonnected thinning).

[L7]

A wonderful anticonnected blockade with small support yields either a y4-restricted induced subgraph or a large anticomplete pair (A wonderful anticonnected complete-or-sparse blockade yields a restricted subgraph or a large anticomplete pair).

Proof

technique · separate the complement-sparse branch from the sparse branch, then resolve the blockade branch by thinning and wonderfulness
1.1

Fix constants from [L1], [L2], and [L4], and set a1:=ac3, a2:=c4, a4:=4, a5:=h+4, and a3:=max{a(c1+5),ac8,c5,4d+1}. These choices depend only on F.

L1L2L4choose
2.1

If Gya3, then any one-vertex induced subgraph of G is y4-restricted and has size at least ya3G. So outcome 2 holds.

step 1.1givenalgebra
2.2

Suppose G is y-sparse. Apply [L2] to the family F inside G with the parameter b=4. Either G has a y4-restricted induced subgraph of size at least y4d+1G, or there are disjoint sets X,YV(G) with Xy4d+1G, Y(1hy)G, and Y anticomplete to X in G. By [L3], the restricted induced subgraph is also y4-restricted in G, and the anticomplete pair in G is a complete pair in G. Since a34d+1 and a5h, this gives outcome 2 or outcome 4 in G.

L2L3step 1.1givenalgebra
2.3

We may therefore assume that G itself is y-sparse. Put ϵ:=ya, where a is the witness from [L4]. Because G is F-free, [L1] applies to G and ϵ. If [L1] produces a clique or stable set of size (ϵc3G)c4, then this is exactly outcome 1 by the choice a1=ac3 and a2=c4. If [L1] produces a complete or anticomplete (k,G/kc5)-blockade with kϵc6, then ky1 because c61, and G/kc5G/ka3 because a3c5, so outcome 3 holds. If [L1] produces an ϵc7-restricted induced subgraph of size at least ϵc8G, then ϵc7y4 and ϵc8=yac8ya3, so outcome 2 holds. We are left only with the blockade alternative from [L1].

L1step 1.1givenalgebra
3.1

Thus G has a blockade A=(A1,,A) with =ϵ1, each Aim:=ϵc1G, and every distinct pair complete or weakly ϵc2-sparse. Apply [L5] to obtain equal-sized subblocks D=(D1,,D) with Di=q:=ϵm and every noncomplete pair mutually ϵc25-sparse. Then apply [L6] to D. If [L6] yields a complete (,q/2)-blockade, then q/2ϵmϵ4=ϵ5m=ya(c1+5)Gya3G, because =ϵ1ϵ2 for ϵ(0,12) and step 1.1 has a3a(c1+5). Since also ϵ1=yay1, outcome 3 follows.

L5L6step 2.3step 1.1choosealgebra
4.1

We may therefore assume [L6] yields anticonnected subsets BiDi of common size w:=q/ such that every distinct pair is either complete or mutually (ϵc25)-sparse. Because ϵ2, every noncomplete pair is in fact mutually ϵc27-sparse. Also wq/ϵ3m=ϵc1+3G=ya(c1+3)Gya3G, since qϵm and ϵ2. Since step 2.1 fails, G>ya3, and because a3a(c1+5) with ϵ=ya, this gives m=ϵc1G>y5a=ϵ5 and hence q=ϵm>ϵm>ϵ4ϵ2. Therefore V(B)=i=1Bi(q/+1)=q+2q2m4mϵc12GϵGyG, where B:=(B1,,B). Since c28, one has ϵc27=ya(c27)ya. Therefore the hypotheses of [L7] hold for B.

step 2.1step 3.1L6L7step 1.1algebra
5.1

Applying [L7] to B yields either a y4-restricted induced subgraph of size at least w, giving outcome 2, or disjoint sets X,YV(G) with X=wya3G, Y(14y)G(1a5y)G, and Y anticomplete to X, giving outcome 4.

L7step 4.1step 1.1algebra
6.1

The cases in steps 2.1, 2.2, 2.3, and 5.1 exhaust all possibilities, so one of the four stated outcomes always holds.

step 2.1step 2.2step 2.3step 5.1

Depends on

Used by

Dependency tree · two levels

28 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