TUHH / Institut für Mathematik / Forschungsgebiete / Connector-Breaker games on random boards Englische Flagge

Connector-Breaker games on random boards

Working Groups: Lehrstuhl Diskrete Mathematik

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

Collaborators (External): Laurin Kirsch

Description

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)}\).

References

[1] D. Clemens, L. Kirsch, and Y. Mogge. Connector-Breaker games on random boards, arXiv:1911.01724 (2019), accepted for publication in Electron. J. Combin.