Connector-breaker games on random boards

Dennis Clemens¹ ; Laurin Kirsch ; Yannick Mogge²

¹Hamburg University of Technology
²Technische Universität Hamburg

The electronic journal of combinatorics, Tome 28 (2021) no. 3

Résumé

By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $G\sim G_{n,p}$ is well studied. Recently, London and Pluhár suggested a variant in which Maker always needs to choose her edges in such a way that her graph stays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $G\sim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Maker's bias to be 1. However, they observed that the threshold biases of both versions played on $K_n$ are still of the same order if instead Maker is allowed to claim two edges in every round. Naturally, this made London and Pluhár ask whether a similar phenomenon can be observed when a $(2:2)$ game is played on $G_{n,p}$. We prove that this is not the case, and determine the threshold probability for winning this game to be of size $n^{-2/3+o(1)}$.

Détail

DOI : 10.37236/9381

Classification : 05C57, 05C40, 05C80, 91A43
Mots-clés : maker-breaker connectivity game, binomial random graph model