Games on Graphs and Other Combinatorial Problems

In this dissertation, we consider various combinatorial problems. The four chapters after the Introduction concern games on graphs, while latter on, we make progress on some questions in the settings of Rademacher sums and graph theory. In Chapter 2, we study the $(m,b)$ Maker-Breaker percolation game. This game, played by two players on the square lattice, was introduced by Day and Falgas-Ravry. The outcome of this game depends crucially on the parameters $m$ and $b$. Day and Falgas-Ravry showed that Breaker wins whenever $b \geq 2m$, but their approach then faces a barrier. We introduce a new, more global approach to study this game and to improve their results: we show that Breaker can in fact guarantee victory whenever $b \geq (2-1/14+o(1))m$. We also show that Breaker can win very fast in a different variant of this game as long as $b \geq 2m$. %We show that Breaker wins whenever $b \geq (2-1/14+o(1))m$, improving the results of Day and Falgas-Ravry and breaking certain barrier arising in their approach. We also show that Breaker can win very fast in a different variant of this game as long as $b \geq 2m$. In Chapters 3 and 4, we look at the Waiter-Client K_k-factor game, first studied by Clemens et al. Here, it is known that Waiter wins, and the question is how long the game will last if Waiter aims to win as fast as possible, Client tries to delay her as much as possible, and both players play optimally. In Chapter 3, we determine the duration of the game under the optimal play of both players when $k=3$, resolving the conjecture of Clemens et al. After that, we study the game for large $k$ in Chapter 4, and obtain the first known non-trivial lower bound for its duration in this case. In Chapter 5, we consider the so-called restricted online Ramsey numbers, which correspond to a certain colouring game in the Builder-Painter setup. We provide a tight lower bound for the restricted online Ramsey numbers of matchings as long as the number of the allowed colours is small, resolving the conjecture of Briggs and Cox. The setting in the next two chapters is the following. Set X=\sum_i=1ⁿ a_i \varepsilon_i, where \varepsilon_i are Rademacher random variables, i.e.~independent, identically distributed random variables taking values $\pm 1$ with probabilities $1/2$ each, and \lbrace a_i \rbrace are arbitary real numbers. In Chapter 6, we make progress towards an old conjecture of Tomaszewski, which concerns concentration of such random variables $X$. In Chapter 7, we study the reverse problem and build up a framework that allows us to show anti-concentration results for Rademacher sums, and in turn we significantly improve the known results in this setting. In Chapter 8, we obtain the best possible bounds for the following problem, first studied by Erd\H{o}s, Pach, Pollak and Tuza: given a connected, triangle-free graph on $n$ vertices and of minimum degree at least δ, how large can the radius of such a graph be? We also study the variant of this problem in which the triangle-free condition is replaced by a condition about the girth of our graph. In Chapter 9, we construct P_n-induced-saturated graph for each $n \geq 6$, answering the question of Axenovich and Csik\'os. Finally, in Chapter 10, we obtain a result about the existence of the antipodal paths with few colour changes in a two-colouring of the edges of the hypercube graph.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2022

Author dc:creator

• Dvorak, Vojtech

Advisor dc:contributor.advisor

• Bollobas, Bela

• combinatorial games
• graph theory
• Rademacher sums

Licence

• https://creativecommons.org/licenses/by/4.0/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.89215

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/341791