First-Order Model Checking on Monadically Dependent Graph Classes

arXiv:2611.08143 · cs.LO, cs.DM, cs.DS, math.CO, math.LO · Submitted 2026-11-05 · Read on arXiv

cs.LO, cs.DM, cs.DS, math.CO, math.LO

Submitted: 2026-11-05

Updated: 2026-11-05

License: http://creativecommons.org/licenses/by/4.0/

The gist: Monadically dependent graph classes are those in which first-order logic cannot encode all graphs.

Terminology

Abstract

Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives a complete characterization of the hereditary graph classes with fixed-parameter tractable first-order model checking. This resolves a central open problem in algorithmic model theory. Our proof combines ideas from structural graph theory (graph decompositions), finite model theory (locality of first-order logic), and model theory (counting types). In particular, we show that in monadically dependent classes, tuples of fixed length have only U O(1) types of fixed quantifier rank over any set of parameters U.

Sources

Related papers