Open Collections

On equality of two classes of homomorphism-homogeneous relational structures

Banff International Research Station for Mathematical Innovation and Discovery

This talk provides a story of equality of homomorphism-homogeneous classes. Cameron and Nesetril [1] suggested a novel notion of homomorphism-homogeneity for relational structure that requires every local homomorphism between finite induced substructures extends to homomorphism to the whole structure extending thus a classical notion of ultrahomogeneity in sense of Fraisse. Depending on types of local homomorphism as well as the extending one it is possible to define various types of homomorphism-homogeneity, e.g. monomorphism-homogeneity extending local monomorphism to homomorphism. Mentioned work was an onset of wide classification program attempting to describe corresponding homogeneity classes. Already in this work there was a question about equality of classes HH and MH which was answered by Rusinov and Schweitzer 4 years later for countable undirected grahs. Later, with Hubicka and Masulovic [3] we studied L-colored graphs, graphs having their edges as well as vertices colored by partial ordered set L, and showed conditions under which classes HH and MH are equal for finite L-colored graphs. We extend this result by considering countably infinite P,Q-colored graphs, graphs coloring vertices and edges by two different partially ordered sets P and Q, and showed that necessary as well as suffcient condition for equality of classes MH and HH is that Q is a linear order [4].
Joint work with Andres Aranda.
[1] P. J. Cameron, J. Nesetril (2006), Homomorphism-homogeneous relational structures, Combinatorics, probability and computing 15(1-2): 91{103.
[2] M. Rusinov, P. Schweitzer (2010), Homomorphismhomogeneous graphs, Journal of Graph Theory 65(3):253{262.
[3] D. Hartman, J. Hubicka, D. Masulovic (2014) Homomorphism-homogeneous L-colored graphs, European Journal of Combinatorics 35: 313{32.
[4] A. Aranda, D. Hartman (2018), Morphism extension classes of countable L-colored graphs. Preprint at arXiv:1805.01781.

Mathematics; Mathematical logic and foundations; Combinatorics

video/mp4

Author affiliation: Charles University in Prague

2019-05-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/70206

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/