Original title:
Rozšiřující vlastnosti struktur
Translated title:
Extension property of structures
Authors:
Hartman, David ; Nešetřil, Jaroslav (advisor) ; Pultr, Aleš (referee) ; Woodrow, Robert (referee) Document type: Doctoral theses
Year:
2014
Language:
eng Abstract:
[eng][cze] 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...Tato práce rozebírá vlastnost relačních struktur, která implikuje jejich vysokou symetričnost. Strukturu nazveme homogenní pokud lze libovolné lokální zobrazení rozšířit na zobrazení nad celou strukturou a to pro li- bovolnou volbu konečné vzorové množiny. Typ lokálního a globálního zo- brazení potom určuje různé typy homogenity. Prominentní místo má ul- trahomogenita, která označuje strukturu, pro kterou libovolný lokální iso- morfismus nad konečnými podstrukturami je rozšiřitelný na automorfismus. Na rozdíl od grafů je klasifikace ultrahomogenních relačních struktur stále otevřeným problémem. Cílem práce je charakterizovat "vzdálenost" od ho- mogenity a to dvěma způsoby. Nejprve zvyšuje "složitost struktury" přidáváním relací a sleduje změny klasifikace homogenních struktur. To vede k několika klasifikacím homomorfně-homogenních L-obarvitelných grafů pro různé L, kde L-obarvitelný graf je graf, kde vrcholy a hrany dostávají množiny barev z částečně uspořádané množiny L. Na to navazují výsledky a diskuze nad hier- archií tříd definovanou skrze různé typy homogenity s ohledem na koincidenci jednotlivých tříd. Druhý pohled zkoumá pro dané struktury jak minimálně rozšířit jejich jazyk, abychom dosáhli homogenity....
Keywords:
colored graphs; complex networks; homomorphism-homogeneous structures; relational complexity; relational structures; ultrahomogeneous structures; homomorfně homogenní struktury; komplexní sítě; obarvené grafy; relační složitost; relační struktury; ultrahomogení struktury
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/65434