Asymptotic Theories of Classes Defined by Forbidden Homomorphisms

2022/04/04 by Bodirsky, Manuel, Jahel, Colin
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2204.01404

Abstract

We study the first-order almost-sure theories for classes of finite structures that are specified by homomorphically forbidding a set 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 sets 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.

Related

• Polyadic Sets and Homomorphism Counting
• Non-Homogenizable Classes of Finite Structures
• Universal structures with forbidden homomorphisms
• Counting Bounded Tree Depth Homomorphisms
• Relativised homomorphism preservation at the finite level