Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedverified 2026-09-24 (gpt-6-sol)
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 sparse host has many leaf extensions, few smaller copies, or a long sparse blockade

Statement

Let H be a finite graph on h≥3 vertices with leaf v, and put H′=H−v. Let a≥2 and 0<x≤y≤4−h. Suppose a finite graph G on n≥1 vertices has maximum degree at most y2n. Then at least one of the following holds:

  1. ind⁡H(G)>x2a+2hnh;
  2. some S⊆V(G) has ∣S∣≥y2n and ind⁡H′(G[S])≤ya−2∣S∣h−1;
  3. G has an x-sparse blockade of length at least y−1 and width at least ya+1n.

Facts & Assumptions

Given: The data in the statement.

[L1]

With parameters x≤y≤(2h)−1, the preceding leaf-extension lemma gives many H-embeddings, a set with few H′-embeddings, or a sparse pair with first side of size at least ya times the host order and second side of size at least (1−hy) times that order (A sparse host has many leaf extensions, few smaller copies, or a sparse pair). The bound 4−h≤(2h)−1 holds for h≥3.

Proof

technique · maximal sparse blockade
1.1

Suppose all three outcomes fail. If y2n≤1, a singleton gives outcome 2 since ∣H′∣≥2. If ya+1n≤1≤y2n, a greedy stable-set algorithm gives at least n/(1+y2n)≥(2y2)−1≥y−1 stable vertices: each selected vertex removes itself and at most y2n neighbors. Taking those vertices as singleton blocks gives outcome 3. Consequently ya+1n>1.

givenalgebra
2.1

Among sequences (B0,…,Bk) of disjoint nonempty sets with Bi x-sparse to every earlier block, ∣Bi∣≥ya+1n for i<k, and ∣Bk∣≥(1−hy)kn, choose one with maximum k. Such a sequence exists with k=0 and B0=V(G); finiteness bounds k. Since outcome 3 fails, k<y−1. For 0≤t≤1/2, 1−t≥4−t (for example, log⁡(1−t)+tlog⁡4 is concave and nonnegative at both endpoints). As hy≤1/2, this gives |B_k|\ge(1-hy)^kn\ge4^{-hyk}n>4^{-h}n\ge yn\ge xn.\tag{1}

step 1.1algebra
3.1

The graph G[Bk] has maximum degree at most y2n≤y∣Bk∣ by (1). Failure of outcome 1 and (1) give ind⁡H(G[Bk])≤ind⁡H(G)≤x2a+2hnh≤x2a+h∣Bk∣h. Because ∣Bk∣>yn≥y2n, failure of outcome 2 gives ind⁡H′(G[Bk])>ya−2∣Bk∣h−1. Thus [L1] applied to G[Bk] supplies disjoint A,B⊆Bk such that ∣A∣≥ya∣Bk∣≥ya+1n, ∣B∣≥(1−hy)∣Bk∣≥(1−hy)k+1n, and B is x-sparse to A.

step 2.1L1
4.1

Replace the old final block Bk by A,B. Since every vertex of Bk was x-sparse to each earlier block, the same is true of its subsets A and B; the new last pair is sparse by step 3.1. The new sequence satisfies all the size conditions of step 2.1 with index k+1, contradicting maximality. Therefore at least one stated outcome holds.

step 2.1step 3.1∎

Depends on

Used by

Dependency tree · two levels

7 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