On the odd cycle game and connected rules
Corsten, Jan; Mond, Adva; Pokrovskiy, Alexey; Spiegel, Christoph; and Szabó, Tibor
(2020)
On the odd cycle game and connected rules
European Journal of Combinatorics, 89: 103140.
ISSN 0195-6698
We study the positional game where two players, Maker and Breaker, alternately select respectively 1 and b previously unclaimed edges of Kn. Maker wins if she succeeds in claiming all edges of some odd cycle in Kn and Breaker wins otherwise. Improving on a result of Bednarska and Pikhurko, we show that Maker wins the odd cycle game if b≤((4−6)∕5+o(1))n. We furthermore introduce “connected rules” and study the odd cycle game under them, both in the Maker–Breaker as well as in the Client–Waiter variant.
| Item Type | Article |
|---|---|
| Departments | Mathematics |
| DOI | 10.1016/j.ejc.2020.103140 |
| Date Deposited | 08 Jul 2020 09:57 |
| URI | https://researchonline.lse.ac.uk/id/eprint/105568 |
Explore Further
-
picture_as_pdf -
subject - Accepted Version
-
- Available under Creative Commons: Attribution-NonCommercial-No Derivative Works 4.0
Download this file
Share this file
Downloads