Pseudo-finiteness of arbitrary graphs of bounded shrub-depth

Abstract

We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the classes ${\mathrm{TM}}_r(d)$ of arbitrary graphs that have tree models of height $d$ and $r$ labels. We show that the graphs of ${\mathrm{TM}}_r(d)$ are $\mathrm{MSO}$-pseudo-finite relative to the class ${\mathrm{TM}}_r^{\text{f}}(d)$ of finite graphs of ${\mathrm{TM}}_r(d)$; that is, that every $\mathrm{MSO}$ sentence true in a graph of ${\mathrm{TM}}_r(d)$ is also true in a graph of ${\mathrm{TM}}_r^{\text{f}}(d)$. We also show that ${\mathrm{TM}}_r(d)$ is closed under ultraproducts and ultraroots. These results have two consequences. The first is that the index of the $\mathrm{MSO}[m]$-equivalence relation on graphs of ${\mathrm{TM}}_r(d)$ is bounded by a $(d+1)$-fold exponential in $m$. The second is that ${\mathrm{TM}}_r(d)$ is exactly the class of all graphs that are $\mathrm{MSO}$-pseudo-finite relative to ${\mathrm{TM}}_r^{\text{f}}(d)$.

17 pages. arXiv admin note: substantial text overlap with arXiv:2010.05799