Proof of `Monadically dependent classes have almost linear neighborhood complexity`

groundedproofs/Lax5Proofs/Theorem2.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

Monadically dependent graph classes have almost linear neighborhood complexity: Theorem 2 of Dreier, Mählmann, McCarty, Pilipczuk and Toruńczyk.

Proof strategy

Choose one representative vertex per realized neighborhood trace on AA; the representatives leave pairwise distinct traces, so the semi-induced form of Lemma 21 bounds their number — which is exactly traceCountGAtraceCount G A — by c · |A|^(1+ε). The paper's reduction to a monadically dependent class of twin-free bipartite graphs lives inside the proof of Lemma 21, whose terminal-sparsification step composes the two assumed statements of this submission (Corollary 6a and Corollary 6b) rather than containing their proofs.

Attribution

Theorem 2 of Dreier, Mählmann, McCarty, Pilipczuk and Toruńczyk, Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes (2026), proved there in Appendix A by the VC-dimension sparsification argument.