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

Stable-tree decomposition conjecture. If $\langle K,\prec_K\rangle$ satisfies $P_1,\ldots,P_n$, then for every sufficiently large $M\in K$ there exist a finite tree…

Let $\mathcal{C}$ be a hereditary class of finite graphs. Lopez's path-transduction conjecture. If $\mathcal{C}$ is not $2$-well-quasi-ordered, then $\mathcal{C}$ existentially tra…

Let $\mathcal{C}$ be a hereditary class of graphs. FO model-checking conjecture. There is an FPT first-order model-checking algorithm for graphs in $\mathcal{C}$ if and only if…

An extensional ESO sentence $\Phi$ defines a decision problem by asking whether the sentence holds on the input structure. Extensional ESO NP-intermediate conjecture. There is an e…

A countable signature $\sigma$ and a class $\mathscr C$ of $\sigma$-structures are given. A unary expansion of $\mathscr C$ is obtained by adding unary relation symbols. Monadic NI…

Let $\mathsf{MSO}^\phi(\sharp)$ be monadic second-order logic with the Härtig quantifier, and call an arithmetical predicate directly definable when it is defined by the logic in t…

Stable transduction conjecture. A hereditary class of graphs is stable if and only if it is a transduction of a nowhere dense class of graphs.

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…

Homogeneous-structure conjecture. (i) Let $M$ be a homogeneous structure over a finite relational language $L$. Then there is an m.e.c. with ultraproduct elementarily equivalent to…

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…

Quadratic EPPA conjecture. The graph $G$ is either a subgraph of a finite homogeneous graph, or every EPPA-witness of $G$ has at least

Siggers-behavior conjecture. Dropping the requirement that ${\bf A}$ has all $1$-cycles should yield a necessary and sufficient condition for solvability of…

Let … scr D$ be infinite classes of finite graphs. An FO-transduction interprets graphs using first-order formulas, while an FOM-transduction allows first-order formulas with modul…

The monadic dependence conjecture. For every hereditary class $d4a2$ of structures, FO model checking is FPT on $d4a2$ if and only if $d4a2$ is monadically dependent.

Finite representation property conjecture. The signature $\tau$ has the finite representation property if and only if

Hereditary-discrepancy characterization. A monotone class $\mathscr{C}$ is nowhere dense if and only if, for every partitioned formula $\varphi(\bar{x};\bar{y})$, every…

Let $\mathscr C$ be a hereditary class of structures. A class is monadically NIP if it remains NIP after arbitrary unary predicates are added. Hereditary first-order model-checking…

For each positive integer $n$, let $_n$ be the class of graphs of pathwidth at most $n$, and let $_n$ be the class of graphs of treewidth at most $n$. Two graph classes are non-com…

Let ${\bf G}^n(G,H)$ be the Seurat game with $n$ colours played on digraphs $G$ and $H$, with players $\forall$ and $\exists$, where $\forall$ seeks to distinguish non-isomorphic d…

Let $k\ge 1$. Fix a set $\Gamma$ of colours and consider graphs $G$ whose colour interpretations satisfy $\operatorname{rg}(\gamma^G)\subseteq\Gamma$. For graphs $G,G'$ and a finit…

Let $A$ be a finite integral relation algebra (RA), and suppose that $A$ has a flexible atom. A relation algebra is representable over a finite cyclic group if it embeds into a Com…

Let $G$ be a graph, let $\phi(\mathcal{X})$ be a C$_2$MS formula, and let $\alpha$ be an assignment to its free variables. Write $\operatorname{qr}(\phi)$ for the quantifier rank o…

Let $\mathcal{D}$ be a graph class, and for every FO formula $\psi(x,y)$ let $F_\psi$ be a graph such that $F_\psi$ is not an induced subgraph of any member of…