Original title: Stuctural Aspects of Graph Homomorphisms
Translated title: Stuctural Aspects of Graph Homomorphisms
Authors: Bok, Jan ; Nešetřil, Jaroslav (advisor) ; Hubička, Jan (referee)
Document type: Master’s theses
Year: 2017
Language: eng
Abstract: [eng] [cze]
This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1 Tato diplomová práce se zabývá náhodnými procházkami, Lipschitzovskými zobrazeními a grafovými homomorfismy. Diskutujeme propojení těchto pojmů, dáváme přehled dosavadních výsledků a ukazujeme nové výsledky. Grafový homomorfismus je zobrazení mezi dvěma grafy zachovávající sousednost. Hlavním předmětem zkoumání jsou pro nás homomorfismy grafů do nekonečných cest. Konkrétně nás zajímají dva parametry: maximální rozsah a průměrný rozsah. Průměrný rozsah grafu je očekávaná velikost obrazu uniformně a náhodně zvoleného homomorfismu do nekonečné cesty. Ukazujeme, jak odvodit vztahy pro výpočet průměrného rozsahu na různých třídách grafů a zabýváme se hlavními hypotézami, které se týkají tohoto parametru. Pro maximální rozsah ukazujeme přesný vztah a způsob výpočtu na obecném grafu. Kromě toho studujeme problém rozšiřování částečného homomorfismu, kde ukážeme jeho polynomialitu pro některé případy. 1
Keywords: graphs; homomorphisms; Lipschitz mappings; random walks; graphs; homomorphisms; Lipschitz mappings; random walks

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/90408

Permalink: http://www.nusl.cz/ntk/nusl-365004


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses