The FO model-checking conjecture for monadically dependent hereditary graph classes

Let C\mathcal{C} be a hereditary class of graphs. FO model-checking conjecture. There is an FPT first-order model-checking algorithm for graphs in C\mathcal{C} if and only if C\mathcal{C} is monadically dependent. This is described as a major conjecture in finite model theory; the equivalence is presented as the unresolved implication underlying the paper's dichotomy, while the surrounding discussion also invokes the assumption FPTAW[]{\mathsf{FPT}}\neq {\mathsf{AW}[*]} for the corresponding algorithmic characterization.

Sources & referencesView supporting material

Primary source

Colin Geniet, Gunwoo Kim and Lucas Meijer, “First-Order Logic and Twin-Width for Some Geometric Graphs”, arXiv:2512.21896 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.