Název: Online Ramseyova teorie
Překlad názvu: Online Ramsey Theory
Autoři: Dvořák, Pavel ; Valla, Tomáš (vedoucí práce) ; Koucký, Michal (oponent)
Typ dokumentu: Diplomové práce
Rok: 2015
Jazyk: eng
Abstrakt: [eng] [cze]
An online Ramsey game is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the fixed graph H, otherwise Painter is the winner. In this thesis we investigate the computational complexity of the related decision problem and we show that it is PSPACE-complete. Moreover, we study a version of the game when Builder can draw only planar graphs and a generalization of the game for hypergraphs. We found a new class of graphs unavoidable on planar graphs. We provide a result showing that Builder wins the online Ramsey game on 3-uniform hyperforests when the goal graph H is 1-degenerate. 1 Online Ramseyho hra je hra dvou hráčů, označovanými jako Builder a Painter. V každém kole Builder postaví hranu grafu a Painter ji nabarví červeně nebo modře. Builder vyhraje, pokud se po nějakém kole objeví v nabarveném grafu jednobarevná kopie daného grafu H, jinak vyhraje Painter. V této práci zkoumáme výpočetní složitost odvozeného rozhodovacího problém a ukážeme, že je PSPACE-úplný. Navíc se zabýváme verzí hry, kdy Builder může stavět jen rovinné grafy, a zobecněním hry pro hypergrafy. Nalezli jsme novou třídu grafů nevyhnutelných na rovinných grafech. Ukázali jsme, že Builder vyhraje online Ramseyho hru na 3-uniformních hyperlesech, pokud je cílový graf H je 1-degenerovaný. 1
Klíčová slova: online Ramseyho hra složitost strategie; online Ramsey game complexity strategy

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

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


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