Proof of `Few atomic types in balls avoiding a closure`
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.
In the paper
- page 23 of this submission's paper
Description
The proof in the paper. For each symmetric let express distance at most in , using the
quantifier-free edge formula of the flip. Let exceed all the bounds
on -patterns and put . For every , every and every base fix a -pattern of maximum
height (less than ), and let consist of and all their grid
points. If a ball in avoids but
realizes more than atomic types over , the matching theorem gives
atomically matched tuples in and of length . By
pigeonhole of the pairs have the same pair of atomic types over
, so on them agrees with or with its complement, and this
yields such that the tuple from and the tuple ū from
satisfy and for . Then and ū
extend the chosen pattern with base by a row, as ū lies in
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.