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.
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 ; the representatives leave pairwise distinct traces, so the semi-induced form of Lemma 21 bounds their number — which is exactly — 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.