Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-adaptedverified 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.

Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph

Statement

Let F be a leaf-reducible finite family of graphs. Then there exist constants d>0 and h≥1 such that for every y∈(0,12), every b>1, and every y-sparse F-free graph G, at least one of the following holds:

  1. there are disjoint sets X,Y⊆V(G) with ∣X∣≥ybd+1∣V(G)∣,∣Y∣≥(1−hy)∣V(G)∣, and Y anticomplete to X; or
  2. G has a yb-restricted induced subgraph with at least ybd+1∣V(G)∣ vertices.

Facts & Assumptions

Given: A leaf-reducible family F, b>1, y∈(0,1/2), and a nonempty y-sparse F-free graph G on n vertices.

[L1]

Leaf-reducibility gives H∈F and a leaf v such that F′={H−v}∪(F∖{H}) has the Erdős-Hajnal property (Leaf-reducible finite graph families).

[L2]

The Erdős-Hajnal property of a finite family implies its virality (For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

[L3]

The leaf-extension counting lemma gives, in a y-sparse host, many H copies, few H−v copies in a set of size at least yn, or a pair A,B with ∣A∣≥yan, ∣B∣≥(1−∣H∣y)n, and B x-sparse to A (A sparse host has many leaf extensions, few smaller copies, or a sparse pair).

Proof

technique · direct
1.1L1L2given

Fix H,v from [L1], put r=∣H∣, and choose a viral exponent D≥1 for F′ by [L2]. If r=2, then H is an edge, so the H-free graph G is stable and its whole vertex set is 0-sparse. Taking d=h=1 gives outcome 2 for all y,b. Hence assume r≥3 and set d=D(r−1)+2 and h=2r. These constants depend only on F.

2.1step 1.1L3givenalgebra

If y≥(2r)−1, then (1−hy)n≤0. Taking X=V(G) and Y=∅ gives outcome 1, since ybd+1≤1. Hence assume y<(2r)−1. Put x=min⁡{y/2,(2n)−1}>0 and a=bD(r−1)+3. Then x≤y, a≥2, and [L3] applies. Its many-H outcome is impossible because G is F-free.

3.1step 1.1step 2.1L2L3algebra

Suppose the few-H−v outcome of [L3] holds. It gives S⊆V(G) with ∣S∣≥yn and ind⁡H−v(G[S])≤ya−2∣S∣r−1<ybD(r−1)∣S∣r−1, since a−2=bD(r−1)+1 and y<1. Every unchanged member of F′ belongs to F, so it has zero copies in G[S]. The viral premise for F′ therefore holds at ϵ=yb. Virality yields a yb-restricted induced subgraph with at least ybD∣S∣≥ybD+1n≥ybd+1n vertices. This is outcome 2.

3.2step 1.1step 2.1L3algebra

Otherwise [L3] gives disjoint A,B with ∣A∣≥yan, ∣B∣≥(1−ry)n≥(1−hy)n, and B x-sparse to A. Since x∣A∣≤xn≤1/2, every vertex of B has integer degree zero into A, so B is anticomplete to A. Also bd+1=bD(r−1)+2b+1≥a because b>1. Thus ∣A∣≥ybd+1n, and X=A,Y=B give outcome 1.

4.1step 2.1step 3.1step 3.2∎

Step 2.1 handles the large-y case, while steps 3.1 and 3.2 exhaust the two remaining alternatives of [L3]. Thus one of the stated outcomes always holds.

Depends on

Used by

Dependency tree · two levels

23 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