6 problems

Let $\mathcal{C}$ be a hereditary class of relational structures. Here, model-checking on $\mathcal{C}$ is tractable if there is an algorithm that, on input a structure…

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-…

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 $\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…