Proof of `Nowhere dense classes are monadically dependent`

groundedproofs/Lax5Proofs/AdlerAdler.lean · lax-5

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

Description

Nowhere dense graph classes are monadically dependent (Adler–Adler).

Proof strategy

Suppose CC 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 CC: a set WW and, for every Boolean pattern on WW, a realizer whose trace on WW is that pattern. Uniform quasi-wideness of a nowhere dense class finds inside WW, after deleting a set SS of at most ss vertices, a subset of any requested size that is pairwise 3(q+2)3^(q+2)-independent in GSG − S. Color every vertex by the rank-bounded local type of its decorated ball in GSG − S, the decorations recording the colors and the adjacency to SS; there are boundedly many types, so a pigeonhole yields s+4s + 4 scattered vertices of one type. The realizers of s+2s + 2 chosen traces are pairwise distinct, so one of them avoids SS, and the ball-swap lemma forces it to be 3q3^q-close to one of the first two scattered vertices and to one of two later ones — two scattered vertices at distance at most 23q<3(q+2)2·3^q < 3^(q+2), 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 Lax5Proofs.QuasiWidenessLax5Proofs.QuasiWideness only reshapes the conclusion from SetSet to FinsetFinset. 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.