Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-01
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.

Star and special-vertex obstructions force wonderfulness

Statement

Let F be a finite family of finite graphs. Assume one of the following.

  1. There exist FF and an integer t1 such that F is an induced subgraph of the 1-subdivision of K1,t.
  2. There exist a graph H on vertex set [q] with 12E(H), with distinguished vertices 1,2, such that {H}F has the Erdős-Hajnal property and H+ is not F-free.

Then F is wonderful.

Facts & Assumptions

Given: A finite family F satisfying one of the two hypotheses in the Statement.

[L1]

To prove that F is wonderful, it suffices to exhibit a constant a6 with the two-outcome property recorded in the definition of wonderfulness (Wonderful finite graph families).

[L2]

Under either obstruction hypothesis, the auxiliary graph on the blocks with 0<NG(v)Bi<12Bi for a fixed outside vertex has a clique or stable set of size at least a positive power of its order (The auxiliary pattern then has a polynomial-size clique or stable set).

[L3]

A polynomial-size clique or stable set in that auxiliary graph yields a y4-restricted union of whole blocks (A polynomial homogeneous set in the auxiliary pattern yields a y4-restricted union).

Proof

technique · follow the source route through the auxiliary graph, but keep the counting and obstruction lifts explicit
1.1

Choose a0:=1 in case 1. In case 2, let a0 be the maximum order of a graph in {H}F. By [L2], fix a constant c(0,1) suitable for the corresponding obstruction hypothesis, and then choose amax{6,a0,5/c+1}.

L2givenchoose
1.2

Let y(0,12), let G be a F-free graph, and let B=(B1,,B) be an (,w)-blockade satisfying the hypotheses from [L1] for the constant a. For each outside vertex xV(G)V(B), define I(x):={i[]:0<NG(x)Bi<12Bi}. Suppose first that I(x)y for every such x. Then the number of pairs (x,i) with xV(G)V(B) and iI(x) is at most yV(G)V(B)yV(G). Averaging over the indices, some i[] is contained in at most yV(G) of the sets I(x). That is exactly the second conclusion from [L1].

L1givenalgebra
2.1

It remains to consider the opposite case. Choose vV(G)V(B) with I(v)y. Let ρ:[s]I(v) be the increasing bijection, where s=I(v), put Cj:=Bρ(j), and form the auxiliary graph J on [s] by ijE(J) if and only if Ci is complete to Cj. The reordered family of blocks still has equal size, still satisfies sy, and still satisfies the pairwise complete-or-mutually-ya-sparse hypothesis. Therefore [L2] applies and gives a clique or stable set R[s] with Rsc.

step 1.1L2choose
3.1

Put R:=ρ(R)I(v). In the auxiliary graph on the original index set I(v), the set R is a clique or stable set with R=RI(v)c. The original blockade B has length ya, the subset I(v) has size at least y, and a5/c+1. Thus [L3] applies to B, I(v), and R. It follows that iRBi induces a y4-restricted subgraph of G whose size is at least the common block size, and therefore at least the width w of B. This is the first conclusion from [L1].

step 1.1step 2.1L1L3
4.1

Step 1.2 gives the second wonderfulness outcome when no outside vertex belongs to many index sets I(x), and step 3.1 gives the first outcome otherwise. Thus the constant a from step 1.1 satisfies [L1], so F is wonderful.

L1step 1.2step 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