On the odd cycle game and connected rules

DOI10.1016/J.EJC.2020.103140MaRDI QIDQ2198973zbMATH OpenOpenAlexFDO

Authors Jan Corsten, Adva Mond, Christoph Spiegel, Tibor Szabó, Alexey Pokrovskiy

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.04024

zbMATH Keywords

client-waiter gamemaker-breaker game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

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 $bleq((4-sqrt6)/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.

Recommendations

• Odd and even cycles in maker-breaker games
• The biased odd cycle game
• An Achievement Game on a Cycle
• On the threshold bias in the oriented cycle game
• Fast winning strategies in maker-breaker games

Cites work

• Asymptotic random graph intuition for the biased connectivity game
• Avoider-Enforcer games
• Avoider-enforcer: the rules of the game
• Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• Biased positional games on matroids
• Combinatorial Games
• Creating cycles in walker-breaker games
• Keeping avoider's graph almost acyclic
• Manipulative waiters with probabilistic intuition
• Odd and even cycles in maker-breaker games
• On the Chvàtal-Erdős triangle game
• Picker-chooser fixed graph games
• Planarity, Colorability, and Minor Games
• Positional games
• Positional games and the second moment method
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Walker-breaker games

Cited in

(8)

• Edge-disjoint odd cycles in graphs with small chromatic numbers
• Raid games across a set with cyclic order
• The biased odd cycle game
• Waiter-client triangle-factor game on the edges of the complete graph
• Connector-breaker games on random boards
• Odd and even cycles in maker-breaker games
• On the threshold bias in the oriented cycle game
• Walker-breaker games on \(G_{n, p}\)

This page was built for publication: On the odd cycle game and connected rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198973)