105 problems

Characterization conjecture. A family of dependencies $\mathcal D$ is strongly first order if and only if every dependency $\mathbf D\in\mathcal D$ is strongly first order.

For $p\in(0,1)$, let $G(n,p)$ be the binomial random graph on $[n]:=\{1,\ldots,n\}$, with each possible edge present independently with probability $p$. An EMSO(FO$^2$) sentence is…

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…

Flexible Atom Conjecture. Every finite integral relation algebra with a flexible atom is representable over a finite set.

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.

A sequence of finite structures is convergent if the satisfaction probability of every formula in the chosen first-order fragment converges. A sequence is residual when, in the ter…

A graph property is CMSOL-definable if it can be expressed by a sentence in counting monadic second-order logic, and it is recognizable if it can be recognized by a finite-state tr…

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…

Dawar's conjecture. For every finitely axiomatizable class $K$ of rigid structures, some formula in the fixed-point extension of first-order logic defines a linear order in $K$.

McColm's conjecture. If every $(\operatorname{FO}+\operatorname{LFP})$ formula is equivalent to a first-order formula in $K$, then every positive elementary induction is bounded in…

Random outerplanar graph conjecture. With probability $1-o(1)$,

Let $\Upsilon$ be a finite vocabulary, and consider finite structures over $\Upsilon$ without a distinguished linear ordering of their underlying sets. A logic in the relevant sens…

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…

CMSO-fragment conjecture.

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…

Extensional ESO is a logical formalism whose sentences define decision problems through existential second-order quantification with extensionality constraints. Extensional ESO dic…

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…

Non-uniformity conjecture. There exist such $\mathfrak{K}$, $\mathbb{P}$, and $\mathfrak{J}$ such that for every $r$ there is a degree bound $d$ for which, for every $t$, there are…

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…

Let $\mathsf{FO}^\phi(\#)$ be first-order logic with the Härtig quantifier, interpreted over finite structures, and let an extension of this logic be given. A limit law means that,…

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

Currently, the focus is on monadically dependent graph classes, that is, graph classes $\mathcal{C}$ such that $\mathcal{G} \not\preceq_{\mathsf{FO}} \mathcal{C}$, where…

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…