Options
Connector-Breaker games on random boards
Citation Link: https://doi.org/10.15480/882.3667
Publikationstyp
Journal Article
Publikationsdatum
2021-07-02
Sprache
English
Institut
TORE-URI
Enthalten in
Volume
28
Issue
3
Article Number
P3.10
Citation
Electronic Journal of Combinatorics 28 (3): P3.10 (2021)
Publisher DOI
Scopus ID
Publisher
EMIS ELibEMS
The Maker-Breaker connectivity game on a complete graph Kn or on a random graph G ∼ Gn,p is well studied by now. 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. It follows from their results that for this connected version of the game, the threshold bias on Kn and the threshold probability on G ∼ Gn,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 Kn are still of the same order if instead Maker is allowed to claim two edges in every round. Naturally, London and Pluhár then asked whether a similar phenomenon can be observed when a (2: 2) game is played on Gn,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).
DDC Class
510: Mathematik
Publication version
publishedVersion
Loading...
Name
9381-PDF file-36693-1-10-20210625.pdf
Size
650.46 KB
Format
Adobe PDF