Repository logo
 

Games on Graphs and Other Combinatorial Problems


Type

Thesis

Change log

Authors

Dvorak, Vojtech 

Abstract

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≥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≥(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≥2m. %We show that Breaker wins whenever b≥(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≥2m.

In Chapters 3 and 4, we look at the Waiter-Client Kk-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=∑i=1naiεi, where εi are Rademacher random variables, i.e.~independent, identically distributed random variables taking values ±1 with probabilities 1/2 each, and {ai} 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 Pn-induced-saturated graph for each n≥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.

Description

Date

2022-06-18

Advisors

Bollobas, Bela

Keywords

combinatorial games, graph theory, Rademacher sums

Qualification

Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge
Sponsorship
Engineering and Physical Sciences Research Council (2260624)