Universial structures with forbidden homomorphisms

DOI10.1515/9781614516873.241MaRDI QIDQ5213570zbMATH OpenOpenAlexFDO

Authors Jan Hubička, J. Nešetřil

Publication date 3 February 2020

Published in Logic Without Borders (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.4079

zbMATH Keywords

amalgamationFraïsséhomomorphism dualityuniversality

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Categoricity and completeness of theories (03C35) Models with special properties (saturated, rigid, etc.) (03C50)

Abstract: We relate the existence problem of universal objects to the properties of corresponding enriched categories (lifts or expansions). In particular, extending earlier results, we prove that for every (possibly infinite) regular set F of finite connected structures there exists a (countable) omega-categorical universal structure U for the class Forb(F) (of all countable structures not containing any homomorphic image of a member of F). We employ a technique known as homogenization: The universal object U is the shadow (reduct) of an ultrahomogeneous structure U'. We also put the results of this paper in the context of homomorphism dualities and constraint satisfaction problems. This leads to an alternative proof of the characterization of finite dualities (given by Tardif and Nev{s}etv{r}il) as well as of the characterization of infinite-finite dualities for classes of relational trees given by P. L. ErdH{o}s, P'{a}lv"{o}lgyi, Tardif and Tardos. The notion of regular families of structures is motivated by the recent characterization of infinite-finite dualities for classes of relational forests (itself related to regular languages). We show how the notion of a regular family of relational trees can be extended to regular families of relational structures. This gives a partial characterization of the existence of a (countable) omega-categorical universal object for classes Forb(F).

Recommendations

• Homomorphism and embedding universal structures for restricted classes
• Forbidden subgraphs and forbidden substructures
• Regular families of forests, antichains and duality pairs of relational structures
• Many Facets of Dualities
• Universal graphs with a forbidden subtree

Cited in

(10)

• Forbidden substructures and combinatorial dichotomies: WQO and universality
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• Homomorphism and embedding universal structures for restricted classes
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Regular families of forests, antichains and duality pairs of relational structures
• Forbidden cycles in metrically homogeneous graphs
• The complexity of resilience problems via valued constraint satisfaction problems
• The complexity of resilience problems via valued constraint satisfaction

This page was built for publication: Universial structures with forbidden homomorphisms

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