Asymptotic Theories of Classes Defined by Forbidden Homomorphisms

MaRDI QIDQ6395600zbMATH OpenFDO

Authors Manuel Bodirsky, Colin Jahel

Publication date 4 April 2022

Abstract: We study the first-order almost-sure theories for classes of finite structures that are specified by homomorphically forbidding a set $mathcalF$ of finite structures. If $mathcalF$ consists of undirected graphs, a full description of these theories can be derived from the Kolaitis-Pr"omel-Rothschild theorem, which treats the special case where $mathcalF=K_n$. The corresponding question for finite sets $mathcalF$ of finite directed graphs is wide open. We present a full description of the almost-sure theories of classes described by homomorphically forbidding finite sets $mathcalF$ of oriented trees; all of them are $omega$-categorical. In our proof, we establish a result of independent interest, namely that every constraint satisfaction problem for a finite digraph has first-order convergence, and that the corresponding asymptotic theory can be described as a finite linear combination of $omega$-categorical theories.

This page was built for publication: Asymptotic Theories of Classes Defined by Forbidden Homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6395600)