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
Copy

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.

picture_as_pdf

picture_as_pdf
subject
Accepted Version
Available under Creative Commons: Attribution-NonCommercial-No Derivative Works 4.0

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads