Online Ramsey Theory

• Thesis title in Czech: Online Ramseyova teorie
• Thesis title in English: Online Ramsey Theory
• Key words: online Ramseyho hra složitost strategie
• English key words: online Ramsey game complexity strategy
• Academic year of topic announcement: 2014/2015
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. RNDr. Tomáš Valla, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 12.11.2014
• Date of assignment: 12.11.2014
• Confirmed by Study dept. on: 02.01.2015
• Date and time of defence: 03.06.2015 09:00
• Date of electronic submission: 29.04.2015
• Date of submission of printed version: 30.04.2015
• Date of proceeded defence: 03.06.2015
• Opponents: prof. Mgr. Michal Koucký, Ph.D.

Guidelines

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

References

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.