Verlagslink DOI: 10.37236/9381
Titel: Connector-Breaker games on random boards
Sprache: Englisch
Autor/Autorin: Clemens, Dennis  
Kirsch, Laurin 
Mogge, Yannick 
Erscheinungs­datum: 2-Jul-2021
Verlag: EMIS ELibEMS
Quellenangabe: Electronic Journal of Combinatorics 28 (3): P3.10 (2021)
Zusammenfassung (englisch): 
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).
URI: http://hdl.handle.net/11420/9906
DOI: 10.15480/882.3667
ISSN: 1077-8926
Zeitschrift: The electronic journal of combinatorics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Lizenz: CC BY-ND 4.0 (Attribution-NoDerivatives) CC BY-ND 4.0 (Attribution-NoDerivatives)
Enthalten in den Sammlungen:Publications with fulltext

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat
9381-PDF file-36693-1-10-20210625.pdfVerlags-PDF650,46 kBAdobe PDFÖffnen/Anzeigen
Miniaturbild
Zur Langanzeige

Seitenansichten

184
Letzte Woche
0
Letzten Monat
7
checked on 01.10.2022

Download(s)

66
checked on 01.10.2022

Google ScholarTM

Prüfe

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons