Tan, Wei En (2017). Waiter–Client and Client–Waiter games. University of Birmingham. Ph.D.
Preview |
Tan17PhD.pdf
PDF - Accepted Version Download (883kB) |
Abstract
In this thesis, we consider two types of positional games; \(Waiter\)-\(Client\) and \(Client\)-\(Waiter\) games. Each round in a biased (\(a\):\(b\)) game begins with Waiter offering a+b free elements of the board to Client. Client claims \(a\) elements among these and the remaining \(b\) elements are claimed by Waiter. Waiter wins in a Waiter-Client game if he can force Client to fully claim a \(winning\) \(set\), otherwise Client wins. In a Client-Waiter game, Client wins if he can claim a winning set himself, else Waiter wins.
We estimate the \(threshold\) \(bias\) of four different (\(1\):\(q\)) Waiter-Client and Client-Waiter games. This is the unique value of Waiter's bias \(q\) at which the player with a winning strategy changes. We find its asymptotic value for both versions of the complete-minor and non-planarity games and give bounds for both versions of the non-\(r\)-colourability and \(k\)-SAT games. Our results show that these games exhibit a heuristic called the \(probabilistic\) \(intuition\).
We also find sharp probability thresholds for the appearance of a graph in the random graph \(G\)(\(n\),\(p\)) on which Waiter and Client win the (\(1\):\(q\)) Waiter-Client and Client-Waiter Hamiltonicity games respectively.
| Type of Work: | Thesis (Doctorates > Ph.D.) |
|---|---|
| Award Type: | Doctorates > Ph.D. |
| Supervisor(s): | Supervisor(s) Email ORCID Perkins, Will UNSPECIFIED UNSPECIFIED Kuhn, Daniela UNSPECIFIED UNSPECIFIED Hefetz, Dan UNSPECIFIED UNSPECIFIED |
| Licence: | |
| College/Faculty: | Colleges > College of Engineering & Physical Sciences |
| School or Department: | School of Mathematics |
| Funders: | None/not applicable |
| Subjects: | Q Science > QA Mathematics |
| URI: | https://bham-theses.eprints-hosting.org/id/eprint/7741 |
Actions
![]() |
Request a Correction |
![]() |
View Item |
Downloads
Downloads per month over past year
Tools
Tools
