Název: Meze pro existenci lichých a jednoznačných expanderů
Překlad názvu: Bounds on existence of odd and unique expanders
Autoři: Hlásek, Filip ; Koucký, Michal (vedoucí práce) ; Šámal, Robert (oponent)
Typ dokumentu: Diplomové práce
Rok: 2016
Jazyk: eng
Abstrakt: [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)
Klíčová slova: liché a jednoznačné expandery; expander graphs; odd and unique expansion

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/78008

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-347525


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce