TUHH / Institut für Mathematik / Forschungsgebiete / Waiter-Client games on random boards Englische Flagge

Waiter-Client games on random boards

Inhalt der Datei randomwc.md

Waiter-Client games on random boards

Collaborators (MAT): Dr. Dennis Clemens, Fabian Hamann, M. Sc., Yannick Mogge, M. Sc.

Collaborators (external): Olaf Parczyk

Biased Waiter-Client games (formerly known as Picker-Chooser games, see e.g. [a]) are a variant of Maker-Breaker games, in which during each round Waiter offers to Client \(b+1\) unclaimed elements of which Client claims one element, while the rest go to Waiter. If by the end of the game Waiter could force Client to occupy all elements of some winning set, she wins the game, otherwise Client wins.

Usually Waiter-Client games are played on a complete graph \(K_n\). Other interesting boards to consider are random graphs. For example one can consider a random graph \(G \sim G_{n,p}\) with \(n\) vertices, where each edge is contained in the graph with probabality \(p\). Another option is to consider games on randomly perturbed graphs, which are the union of a random graph \(G \sim G_{n,p}\) and a deterministic graph \(G_{\alpha}\) with minimum degree \(\alpha\).


[CHMP2020] D. Clemens, F. Hamann, Y. Mogge, and Olaf Parczyk, Positional games on randomly perturbed graphs, arXiv:2009.14583 (2020)

[HKT2017] D. Hefetz, M. Krivelevich, and W. Tan, Waiter?Client and Client?Waiter Hamiltonicity games on random graphs, European Journal of Combinatorics Volume 63, June 2017, 26-43.