11 problems

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.

Stable hereditary graph class characterization conjecture. The following properties are equivalent:

Monadic stability characterization conjecture. A class of graphs is monadically stable if and only if it is a first-order transduction of a nowhere dense class of graphs.

Nešetřil–Ossona de Mendez's strong mass-transport conjecture. Every first-order convergent sequence of graphs from ${\cal C}$ has a modeling limit that satisfies the strong finitar…

Let $\mathcal{C}$ be a nowhere dense class of graphs, let $d$ be a positive integer, and let $\varepsilon$ be a positive real. For a graph $G$, write $G^d$ for its $d$th power, and…

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…

Let $\mathcal{C}$ be a nowhere dense graph class, and let $\mathcal{D}$ be a graph class FO interpretable in $\mathcal{C}$. FO model-checking conjecture. The class $\mathcal{D}$ ha…

The neighborhood-complexity characterization. The class $\mathcal{C}$ is nowhere dense if and only if there exists a function $f_{\mathrm{nei}}(r,\varepsilon)$ such that

The nowhere-dense domination-set kernelization dichotomy. If $\mathcal{C}$ is nowhere dense, then for each $r\in\mathbb{N}$, the textsc{Distance-$r$ Dominating Set} problem admits…

Let $\mathcal C$ be a monotone class of finite graphs, meaning that it is closed under taking subgraphs. A class is nowhere dense in the standard sparse-graph sense. The class…

Let ${\cal C}$ be a nowhere-dense class of graphs. A sequence of graphs from ${\cal C}$ is first order convergent if the limiting frequency of every first-order property exists. A…