Homomorphism and embedding universal structures for restricted classes
arXiv:0909.4939
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 Nešetř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).
27 pages, 4 figures. Reworked version to appear in Journal of Multiple-Valued Logic and Soft Computing
References in corpus (1)
Cited by in corpus (5)
- All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
- Bowtie-free graphs have a Ramsey lift
- Invariant measures concentrated on countable structures
- ω-categorical structures avoiding height 1 identities
- Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)