Proof of `Few atomic types in balls avoiding a closure`

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

Description

The proof in the paper. For each symmetric R⊆Πs×ΠsR ⊆ Π^s × Π^s let φR(zˉx,y)φ_R(z̄ x, y) express distance at most rr in G⊕(zˉ,R)G ⊕ (z̄, R), using the quantifier-free edge formula of the flip. Let kk exceed all the bounds on φRφ_R-patterns and put t=Q(k⋅9s)t = Q(k · 9^s). For every RR, every N∈E,¬EN ∈ {E, ¬E} and every base bˉ∈Akb̄ ∈ A^k fix a (φR,N)(φ_R, N)-pattern of maximum height (less than kk), and let A∗A* consist of AA and all their grid points. If a ball B=BallrH[v]B = Ball^H_r[v] in H=G⊕(pˉ,R)H = G ⊕ (p̄, R) avoids A∗A* but realizes more than tt atomic types over AA, the matching theorem gives atomically matched tuples in BB and AA of length k⋅9sk · 9^s. By pigeonhole kk of the pairs have the same pair of atomic types over pˉp̄, so on them HH agrees with GG or with its complement, and this yields NN such that the tuple wˉw̄ from AA and the tuple ū from BB satisfy N(wj,uj)N(wⱼ, uⱼ) and ¬N(wj′,uj)¬N(wⱼ', uⱼ) for j<j′j < j'. Then pˉvp̄ v and ū extend the chosen pattern with base wˉw̄ by a row, as ū lies in BB and the old grid points do not, contradicting maximality.

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