Research Topic: 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\).
