This work analyses properties of relational structures that imply a high degree of symmetry. A structure is called homogeneous if every mapping from any finite substructure can be extended to a mapping over the whole structure. The various types of these mappings determine corresponding types of homogeneity. A prominent position belongs to ultrahomogeneity, for which every local isomorphism can be extended to an automorphism. In contrast to graphs, the classification of ultrahomogeneous relational struc- tures is still an open problem. The task of this work is to characterize "the distance" to homogeneity using two approaches. Firstly, the classification of homogeneous structures is studied when the "complexity" of a structure is increased by introducing more relations. This leads to various classifications of homomorphism-homogeneous L-colored graphs for different L, where L- colored graphs are graphs having sets of colors from a partially ordered set L assigned to vertices and edges. Moreover a hierarchy of classes of ho- mogeneous structures defined via types of homogeneity is studied from the viewpoint of classes coincidence. The second approach analyses for fixed classes of structures the least way to extend their language so as to achieve homogeneity. We obtain results about relational complexity for finite...
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:334569 |
| Date | January 2014 |
| Creators | Hartman, David |
| Contributors | Nešetřil, Jaroslav, Pultr, Aleš, Woodrow, Robert |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0011 seconds