Games on Graphs and Other Combinatorial Problems
Repository URI
Repository DOI
Change log
Authors
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
In Chapters 3 and 4, we look at the Waiter-Client
In Chapter 3, we determine the duration of the game under the optimal play of both players when
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
In Chapter 6, we make progress towards an old conjecture of Tomaszewski, which concerns concentration of such random variables
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
In Chapter 9, we construct
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.