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

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 h1 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,YV(G) with Xybd+1V(G),Y(1hy)V(G), and Y anticomplete to X; or
  2. G has a yb-restricted induced subgraph with at least ybd+1V(G) vertices.

Facts & Assumptions

Given: A leaf-reducible finite family F, parameters y(0,12) and b>1, and a y-sparse F-free graph G.

[L1]

Because F is leaf-reducible, there exist HF and a leaf vV(H) such that F:={H{v}}(F{H}) has the Erdős-Hajnal property (Leaf-reducible finite graph families).

[L2]

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

[L3]

Deleting a leaf from each of two forbidden graphs preserves virality (Deleting a leaf from each of two forbidden graphs preserves virality).

[L4]

A graph is F-free when it contains no induced copy of any member of F (H-free and F-free graphs under the induced-subgraph convention).

Proof

technique · direct
1.1

By [L1], fix H and v so that the modified family F:={H{v}}(F{H}) has the Erdős-Hajnal property. By the implication from assertion 1 to assertion 3 in [L2], the family F is viral.

L1L2
2.1

Apply [L3] with both leaf-deletion slots equal to the same graph H and with the same leaf v. The two modified families are both F, so step 1.1 makes them viral. Therefore F itself is viral. Using the implication from assertion 3 to assertion 2 in [L2], choose d>0 such that every F-free graph has an ϵ-restricted induced subgraph on at least ϵd times its number of vertices for every ϵ(0,12). Set h:=1.

step 1.1L2L3choose
3.1

Since G is F-free by [L4], step 2.1 applies to G with ϵ:=yb(0,12). We obtain a yb-restricted induced subgraph of G with at least (yb)dV(G)=ybdV(G) vertices. Since y(0,12), one has ybdybd+1, so this induced subgraph also has at least ybd+1V(G) vertices. Hence outcome 2 holds.

step 2.1L4algebra
4.1

Because outcome 2 always holds, the displayed dichotomy is satisfied.

step 3.1

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

22 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