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 F⋆∈F and an integer t≥1 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 12∈E(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 a≥6 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∣<12∣Bi∣ 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.1L2givenchoose

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 a≥max⁡{6,a0,5/c+1}.

1.2L1givenalgebra

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 x∈V(G)∖V(B), define I(x):={i∈[ℓ]:0<∣NG(x)∩Bi∣<12∣Bi∣}. Suppose first that ∣I(x)∣≤yℓ for every such x. Then the number of pairs (x,i) with x∈V(G)∖V(B) and i∈I(x) is at most yℓ∣V(G)∖V(B)∣≤yℓ∣V(G)∣. Averaging over the ℓ indices, some i∈[ℓ] is contained in at most y∣V(G)∣ of the sets I(x). That is exactly the second conclusion from [L1].

2.1step 1.1L2choose

It remains to consider the opposite case. Choose v∈V(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 ij∈E(J) if and only if Ci is complete to Cj. The reordered family of blocks still has equal size, still satisfies s≥yℓ, and still satisfies the pairwise complete-or-mutually-ya-sparse hypothesis. Therefore [L2] applies and gives a clique or stable set R⊆[s] with ∣R∣≥sc.

3.1step 1.1step 2.1L1L3

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′∣=∣R∣≥∣I(v)∣c. The original blockade B has length ℓ≥y−a, the subset I(v) has size at least yℓ, and a≥5/c+1. Thus [L3] applies to B, I(v), and R′. It follows that ⋃i∈R′Bi 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].

4.1L1step 1.2step 3.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.

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