Name
Abstract | ||
|---|---|---|
The Maker-Breaker connectivity game on a complete graph K-n or on a random graph G similar to G(n,p )is well studied by now. Recently, London and Pluhar 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 K-n and the threshold probability on G similar to 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, London and Pluhar then asked 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)). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.37236/9381 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 28 | 3 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Clemens Dennis | 1 | 18 | 8.25 |
| Kirsch Laurin | 2 | 0 | 0.34 |
| Mogge Yannick | 3 | 0 | 0.68 |