On the Odd Cycle Game and Connected Rules

2019/06/10 by Jan Corsten, Adva Mond, Corsten, Jan +7
Mathematics · #05C38 #05C57 #91A24 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38 #msc:05C57 #msc:91A24

paper · pdf · doi:10.48550/arxiv.1906.04024

22 pages, 3 figures

arxiv created 2019/06/10 · arxiv updated 2019/06/11

Abstract

We study the positional game where two players, Maker and Breaker, alternately select respectively 1 and b previously unclaimed edges of K_n. Maker wins if she succeeds in claiming all edges of some odd cycle in K_n 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.

Related

• A Constructive Winning Maker Strategy in the Maker-Breaker C₄-Game
• On the Constructor-Blocker Game
• An Achievement Game on a Cycle
• The biased odd cycle game
• A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck