Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 2157

Preprint Number 2157

Previous Next Preprint server

2157. Manuel Bodirsky and Colin Jahel
Asymptotic Theories of Classes Defined by Forbidden Homomorphisms

Submission date: 4 April 2022


We study the first-order almost-sure theories for classes of finite structures that are specified by homomorphically forbidding a set \mathcal{F} of finite structures. If F consists of undirected graphs, a full description of these theories can be derived from the Kolaitis-Prömel-Rothschild theorem, which treats the special case where F = {K_n}. The corresponding question for finite F 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 F of oriented trees; all of them are ω-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 ω-categorical theories.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2204.01404: pdf, ps.

Last updated: April 21 2022 16:39 Please send your corrections to: