Proof of `Closure theorem`

groundedproofs/Lax185574Proofs/ClosureTheorem.lean · lax-185574

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 21 of this submission's paper

Description

Induction on rr, as in the paper. At radius 0 take A∗=AA* = A and no flip. For the step, enlarge AA to A1A₁ by the ball-types lemma for the current parameter bound ss, and apply the induction hypothesis to A1A₁, giving BB. The ss-definable flips of graphs of the class form a monadically dependent class, so they have VC-dimension at most some dd. For every set S⊆BS ⊆ B of at most ss vertices and every SS-flip HH (at most 29s2^{9^s} of them), group the vertices whose radius-rr ball in HH avoids A1A₁ by the set of atomic types over AA that the ball meets. By the ball-types lemma these profiles have at most tt members, and by the Sauer–Shelah lemma there are at most ∣A∣+(∣A∣+1)d|A| + (|A| + 1)^d atomic types over AA, so there are polynomially many groups. The ball flip lemma gives a zz-definable flip of HH that (r+1)(r + 1)-separates each group from AA, which is an (s+z)(s + z)-definable flip of GG by transitivity. The new closure is A1A₁ together with the parameters of all these flips. Vertices of A1∖AA₁ ∖ A are isolated by the flip over themselves.

The argument is carried out for the graph classes of the archive and their monadic dependence, and transferred to the graph classes used here.