Online Ramsey Theory

• Název práce v češtině: Online Ramseyova teorie
• Název v anglickém jazyce: Online Ramsey Theory
• Klíčová slova: online Ramseyho hra složitost strategie
• Klíčová slova anglicky: online Ramsey game complexity strategy
• Akademický rok vypsání: 2014/2015
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. RNDr. Tomáš Valla, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 12.11.2014
• Datum zadání: 12.11.2014
• Datum potvrzení stud. oddělením: 02.01.2015
• Datum a čas obhajoby: 03.06.2015 09:00
• Datum odevzdání elektronické podoby: 29.04.2015
• Datum odevzdání tištěné podoby: 30.04.2015
• Datum proběhlé obhajoby: 03.06.2015
• Oponenti: prof. Mgr. Michal Koucký, Ph.D.

Zásady pro vypracování

Dva hráči, Builder a Painter hrají hru na vrcholech grafu. Builder ve svém tahu postaví hranu, Painter ji obarví 2 barvami.
Builder vyhraje, pokud donutí Paintera jednobarevně nakreslit jistý předem daný graf H, jinak vyhraje Painter.
Klasická Ramseyova teorie dává nástroje pro studium těchto online problémů, nicméně potřebná velikost
hracího plánu pro vítězství Buildera může být podstatně nižší než odpovídající Ramseyovo číslo.
Existují také problémy v online Ramseyově teorii, které v klasické Ramseyové teorii neplatí.
V poslední době zaznamenalo pozornost odvětví online Ramsey teorie tzv. vynutitelnost tříd grafů.
Cílem této práce je:
* navázat na předchozí výsledky o vynutitelnosti tříd grafů
* zobecnit známé výsledky na hypergrafy a jejich třídy
* zabývat se zobecněním problému na více než 2 barvy
* prozkoumat složitostní aspekty online Ramseyovy teorie

Seznam odborné literatury

D. Conlon: On-line Ramsey numbers, SIAM Journal on Discrete Mathematics 23, 2009.
J. Grytczuk, M. Haluszczak, H. Kierstead: On-line Ramsey Theory, EJC 11, 2004.
Š. Petříčková: Online Ramsey Theory for Planar Graphs, EJC 21, 2014.