The classification of homomorphism homogeneous tournaments

Thomas FellerThomas Feller, Christian PechChristian Pech, Maja PechMaja Pech

Thomas Feller, Christian Pech, Maja Pech
The classification of homomorphism homogeneous tournaments
European Journal of Combinatorics, 89:103142, October 2020

Details
Bibtex

KurzfassungAbstract
The notion of homomorphism homogeneity was introduced by Cameron and Nešetřil as a natural generalization of the classical model-theoretic notion of homogeneity. A relational structure is called homomorphism homogeneous (HH) if every homomorphism between finite substructures extends to an endomorphism. It is called polymorphism homogeneous (PH) if every finite power of the structure is homomorphism homogeneous. Despite the similarity of the definitions, the HH and PH structures lead a life quite separate from the homogeneous structures. While the classification theory of homogeneous structure is dominated by Fraïssé-theory, other methods are needed for classifying HH and PH structures. In this paper we give a complete classification of HH countable tournaments (with loops allowed). We use this result in order to derive a classification of countable PH tournaments. The method of classification is designed to be useful also for other classes of rela- tional structures. Our results extend previous research on the classification of finite HH and PH tournaments by Ilić, Mašulović, Nenadov, and the first author.
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{FPP2020,
  author    = {Thomas Feller and Christian Pech and Maja Pech},
  title     = {The classification of homomorphism homogeneous tournaments},
  journal   = {European Journal of Combinatorics},
  volume    = {89},
  publisher = {Elsevier},
  year      = {2020},
  month     = {October},
  pages     = {103142},
  doi       = {10.1016/j.ejc.2020.103142}
}