Options
Variants of Maker-Breaker games on complete and random graphs
Citation Link: https://doi.org/10.15480/882.14834
Publikationstyp
Doctoral Thesis
Date Issued
2025
Sprache
English
Author(s)
Advisor
Referee
Title Granting Institution
Technische Universität Hamburg
Place of Title Granting Institution
Hamburg
Examination Date
2025-02-18
Institute
TORE-DOI
Citation
Technische Universität Hamburg (2025)
This thesis studies two topics, both of which focus on different variants of positional games.
The first topic is the study of fast strategies in Waiter-Client games played on the edge set of the complete graph. We prove results for unbiased games, where the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees, or factors of a given graph. We also consider the biased versions of the perfect matching game and the Hamiltonicity game.
The second topic is the study of Connector-Breaker and Walker-Breaker games played on the edge set of a random graph. We prove bounds for the threshold probabilities for Walker's and Breaker's strategies.
The first topic is the study of fast strategies in Waiter-Client games played on the edge set of the complete graph. We prove results for unbiased games, where the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees, or factors of a given graph. We also consider the biased versions of the perfect matching game and the Hamiltonicity game.
The second topic is the study of Connector-Breaker and Walker-Breaker games played on the edge set of a random graph. We prove bounds for the threshold probabilities for Walker's and Breaker's strategies.
Subjects
Games on graphs
Trees
Connectivity
Eulerian and Hamiltonian graphs
Random graphs
DDC Class
519: Applied Mathematics, Probabilities
005.1: Programming
Loading...
Name
Variants of Maker-Breaker games on complete and random graphs.pdf
Size
1.75 MB
Format
Adobe PDF