Proof of `Closure theorem for tuples`

groundedproofs/Lax185574Proofs/ClosureTheoremTuples.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 28 of this submission's paper

Description

Apply the closure theorem at radius 6r6r to obtain A∗A* and the sets S(v)S(v). For every T⊆A∗T ⊆ A* of size at most k⋅s0k·s₀, the partition-metric conversion applied to 𝒫T𝒫_T, which has at most 3ks03^{k s₀} parts, gives one flip HTH_T whose radius-rr balls lie in the radius-6r6r balls of the flip metric of 𝒫T𝒫_T. For a tuple vˉv̄ outside AA take T=S(v1)∪…∪S(vk)T = S(v₁) ∪ … ∪ S(v_k). As 𝒫T𝒫_T refines 𝒫S(vi)𝒫_{S(vᵢ)}, the flip metric of 𝒫T𝒫_T dominates that of 𝒫S(vi)𝒫_{S(vᵢ)}, and the latter is at least the distance in the S(vi)S(vᵢ)-flip from the closure theorem, which exceeds 6r6r. So HTH_T separates vˉv̄ from AA at distance more than rr. There are at most (∣A∗∣+1)ks0(|A*| + 1)^{k s₀} sets TT.

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