12 problems

Let ${\mathscr C}$ be a hereditary class of graphs. A class is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from the class using a fixed first-…

Dependence conjecture. First-order model checking is fixed-parameter tractable on every hereditary dependent class of graphs.

Let ${\mathscr C}$ be a hereditary graph class. Say that ${\mathscr C}$ has almost bounded merge-width if, for every fixed $r\in\mathbb{N}$, the radius-$r$ merge-width of its $n$-v…

Monadic NIP characterization. First-order model checking is fixed-parameter tractable on ${\mathcal C}$ if and only if ${\mathcal C}$ has monadic NIP; for hereditary classes of rel…

A class of relational structures is independent when it has the relevant independence property, and it is hereditary when it is closed under induced substructures. A TOWS graph is…

FO model-checking conjecture. First-Order model checking is fixed-parameter tractable on $\mathscr C$ if and only if $\mathscr C$ is dependent.

The monadic dependence model-checking conjecture. For every monadically dependent class $\mathscr{C}$ there is a constant $c\in\mathbb N$ and an algorithm that, given a graph…

Let $C$ be a hereditary graph class. Bounded-rank alternation conjecture. The class $C$ has bounded rank if and only if there is $kinmathbb{N}$ such that every first-order fo…

Let $C$ be a hereditary graph class. For $dinmathbb{N}$, let $Td$ denote the class of all trees of depth $d$. Pilipczuk–Toruńczyk's rank conjecture. The class $C$ has elemen…

Let ${\mathsf{ConStR}}$ be the logic for conditional local strategic reasoning introduced in the paper, and consider the problem of deciding whether a ${\mathsf{ConStR}}$ formula i…

Let $\mathcal{G}$ be a graph class with bounded expansion, let $I$ be a simple first-order graph interpretation scheme, and let $\varphi$ be a first-order property to be tested. Th…

Let the higher-order nested pushdown tree hierarchy consist of nested pushdown trees at all finite levels, equipped with their tree structure and jump relations. The modal $\mu$-ca…