Proof of `Nowhere dense classes are monadically dependent`
groundedproofs/Lax5Proofs/AdlerAdler.lean · lax-5
What this proof establishes
Lax5.AdlerAdlerAssuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Nowhere dense graph classes are monadically dependent (Adler–Adler).
Proof strategy
Suppose transduces all graphs. Then it produces every powerset bipartite graph, so the edge formula of the transduction shatters arbitrarily large vertex sets in colored members of : a set and, for every Boolean pattern on , a realizer whose trace on is that pattern. Uniform quasi-wideness of a nowhere dense class finds inside , after deleting a set of at most vertices, a subset of any requested size that is pairwise -independent in . Color every vertex by the rank-bounded local type of its decorated ball in , the decorations recording the colors and the adjacency to ; there are boundedly many types, so a pigeonhole yields scattered vertices of one type. The realizers of chosen traces are pairwise distinct, so one of them avoids , and the ball-swap lemma forces it to be -close to one of the first two scattered vertices and to one of two later ones — two scattered vertices at distance at most , a contradiction.
The quasi-wideness input is not reproved here: it is assumed from the Sparsity Lectures submission, whose nowhere-denseness definition is the very one this statement is phrased over, so no transport is needed and only reshapes the conclusion from to . Everything below it — shattering, local types, ball swapping and the pigeonhole — is proved here.
Attribution
The theorem is Adler and Adler's, Interpreting nowhere dense graph classes as a classical notion of model theory (European Journal of Combinatorics, 2014), who prove the stronger monadic stability. The proof here is the deletion specialization of the flip-breakability route: uniform quasi-wideness and a semantic locality argument, with rank-bounded local types of decorated balls and a ball-swap back-and-forth in place of Gaifman's theorem.