Homomorphism and embedding universal structures for restricted classes

MaRDI QIDQ4583880zbMATH OpenFDO

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

Publication date 3 September 2018

Full work available at URL https://arxiv.org/abs/0909.4939, http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-27-number-2-3-2016/mvlsc-27-2-3-p-229-253/

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Models with special properties (saturated, rigid, etc.) (03C50) Applications of model theory (03C98)

Abstract: This paper unifies problems and results related to (embedding) universal and homomorphism universal structures. On the one side we give a new combinatorial proof of the existence of universal objects for homomorphism defined classes of structures (thus reproving a result of Cherlin, Shelah and Shi) and on the other side this leads to the new proof of the existence of dual objects (established by Nev{s}etv{r}il and Tardif). Our explicite approach has further applications to special structures such as variants of the rational Urysohn space. We also solve a related extremal problem which shows the optimality (of the used lifted arities) of our construction (and a related problem of A. Atserias).

Recommendations

• Universal realisators for homology classes
• Universial structures with forbidden homomorphisms
• Towards finite homomorphism-homogeneous relational structures
• scientific article; zbMATH DE number 468791
• Embeddings of universal algebras into simple ones
• scientific article; zbMATH DE number 1260942
• Computable embeddability for algebraic structures
• scientific article; zbMATH DE number 1342162
• Homology and universality relative to a functor
• scientific article; zbMATH DE number 4108983

Cited in

(15)

• An algebraic view on p-admissible concrete domains for lightweight description logics
• Using model theory to find decidable and tractable description logics with concrete domains
• ASNP: a tame fragment of existential second-order logic
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• Bowtie-free graphs have a Ramsey lift
• Metrically homogeneous graphs of diameter \(3\)
• \( \omega \)-categorical structures avoiding height 1 identities
• Universial structures with forbidden homomorphisms
• scientific article; zbMATH DE number 2187692 (Why is no real title available?)
• On the descriptive complexity of temporal constraint satisfaction problems
• Homomorphism-homogeneity classes of countable L-colored graphs
• Forbidden cycles in metrically homogeneous graphs
• Homogeneity and homogenizability: hard problems for the logic SNP
• 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: Homomorphism and embedding universal structures for restricted classes

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