Original title: Meze pro existenci lichých a jednoznačných expanderů
Translated title: Bounds on existence of odd and unique expanders
Authors: Hlásek, Filip ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
Document type: Master’s theses
Year: 2016
Language: eng
Abstract: [eng] [cze]
We study the existence of expander graphs with a focus on odd and unique expanders. The main goal is to describe configurations of arguments for which there is no infinite family of expanders. The most imporant result is that for every graph there is a nonempty subset of at most half of its vertices, such that every other vertex is connected at least twice to the subset or not connected to the subset at all. It follows that certain classes of unique expanders cannot exist. On the other hand we present some configurations for which there are families of expanders. Powered by TCPDF (www.tcpdf.org) Práce se zabývá studiem existence expanderů a zaměřuje se především na liché a jednoznačné expandery. Naším nejdůležitějším výsledkem je tvrzení, že v každém grafu lze vybrat malou neprázdnou podmnožinu jeho vrcholů takovou, že každý jiný vrchol je s vybranou podmnožinou spojen alespoň dvěma hranami, nebo s ní není spojen vůbec. Jednoduchým důsledkem tohoto tvrzení je, že některé třídy jednoznačných expanderů nemohou existovat. Na druhou stranu popisujeme konfigurace parametrů, pro které nekonečné třídy expanderů jistě existují. Powered by TCPDF (www.tcpdf.org)
Keywords: expander graphs; odd and unique expansion; liché a jednoznačné expandery

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

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


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