Connector-breaker games on random boards (Q2040008)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connector-breaker games on random boards |
scientific article |
Statements
Connector-breaker games on random boards (English)
0 references
6 July 2021
0 references
Summary: 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, \textit{A. London} and \textit{A. Pluhár} [Acta Cybern. 23, No. 3, 921--927 (2018; Zbl 1413.91017)] 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)}\).
0 references
maker-breaker connectivity game
0 references
binomial random graph model
0 references