Constructive Winning Breaker Strategies in the Maker-Breaker C_k-Game
Pith reviewed 2026-07-03 20:25 UTC · model grok-4.3
The pith
Breaker wins the Maker-Breaker C_k game with a polynomial-time strategy when q exceeds the (k-1)th root of (k-1) times (2(k-1)/k)^{k-2} times n^{k-2}.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
If a potential function satisfies conditions that depend on the target graph C, then Breaker has a winning strategy in the Maker-Breaker game on C. Applying this general criterion to the k-cycle for any fixed k greater than or equal to 4 produces an explicit bias threshold above which Breaker wins: q larger than the (k-1)th root of (k-1) times (2(k-1)/k) to the power k-2 times n to the power k-2. The same argument yields the first polynomial-time strategies for Breaker in these games and improves the constants obtained from random strategies while remaining asymptotically optimal.
What carries the argument
A potential function that fulfills conditions depending on the target cycle C, used to decide Breaker's moves at each step.
Load-bearing premise
The potential function fulfills the conditions depending on C.
What would settle it
A direct check, for fixed small k and moderate n, whether the potential decreases at every step when Breaker follows the rule and q equals the stated root expression.
read the original abstract
Maker-Breaker subgraph games are among the most famous combinatorial games. For $n,q\in\mathbb{N}$ and a fixed subgraph $C$ of the complete graph $K_n$, the two players, called Maker and Breaker, alternately claim edges of $K_n$. Maker claims one unclaimed edge per round and Breaker may claim up to $q$ edges per round. If Maker is able to claim all edges of a copy of $C$, he wins the game. Otherwise Breaker wins. Bednarska and {\L}uczak (2000) determined in a landmark work the asymptotics of the treshold bias as $\Theta(n^{1/m(C)})$ where $m(C)$ is the 2-density of $C$, analysing random strategies. Since then it has been a major open problem to determine the treshhold bias, if it exists, with corresponding strategies, leading to sharp constants in the $\Theta$-notion. A famous case is the triangle game ($C=C_3$), studied by Chvatal and Erd"os (1978), who showed Maker wins if $q\le \sqrt{2n}$ and Breaker wins if $q\ge2\sqrt{n}$. Glazik and Srivastav (2022) improved this via a potential method, showing Breaker wins already for $q\ge\sqrt{8/3}\sqrt{n}$. Spencer (2019) conjectured generalizability to arbitrary subgraphs $C$. We confirm this conjecture, presenting a general winning strategy for Breaker if the potential function fullfils conditions depending on $C$. With this result we give the first constructive (polynomial-time) strategies for Breaker in the $k$-cycle Maker-Breaker game for arbitrary, but fixed $k \geq 4$: Breaker wins if $q>\sqrt[k-1]{(k-1)\big(\frac{2(k-1)}{k}\big)^{k-2}n^{k-2}}$. By Bednarska and {\L}uczak (2000) our bound is asymptotically optimal. However, our constants are better than those arising from their random strategies. More recently, Sowa and Srivastav (2025) gave the first constructive Maker strategy for $C_4$. Our work may motivate study of Maker strategies for $C_k, k \ge 5$, narrowing the gap towards the Breaker bounds presented.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims to confirm Spencer's conjecture by giving a general potential-function strategy that guarantees a win for Breaker in Maker-Breaker games on any fixed subgraph C whenever the potential satisfies a list of C-dependent conditions. Specializing to C = C_k for fixed k ≥ 4, the authors obtain the first explicit constructive (polynomial-time) Breaker strategies, winning whenever q exceeds the (k-1)th root of (k-1)(2(k-1)/k)^{k-2} n^{k-2}; the bound is asymptotically optimal by the Bednarska-Łuczak theorem but improves the leading constant over random strategies.
Significance. If the potential-function conditions are verified for C_k, the result supplies the first constructive Breaker strategies for these games together with improved constants, directly addressing a long-standing open problem on explicit strategies and potentially motivating corresponding constructive Maker results for k ≥ 5.
major comments (2)
- [Abstract / application to C_k] The headline explicit bound for the C_k game rests entirely on the assertion that the chosen potential function satisfies the C-dependent conditions stated for the general strategy. The abstract invokes this fulfillment but supplies no derivation, inequality checks, or error analysis; this verification step is load-bearing for the central claim and must be exhibited explicitly (with all constants tracked) in the section applying the general theorem to cycles.
- [General Breaker strategy] The general strategy is stated to apply only when the potential meets the listed conditions depending on C; without an independent check that these inequalities hold for the specific potential chosen for C_k (including the precise dependence on k), the reduction from the general theorem to the displayed root expression cannot be confirmed.
minor comments (2)
- [Abstract] Abstract contains several typos and nonstandard notation: 'fullfils' → 'fulfils', 'treshhold' → 'threshold', 'root(k-1) of' should be written as the '(k-1)th root of' for clarity.
- [Abstract] The statement 'our constants are better than those arising from their random strategies' would benefit from an explicit numerical comparison for at least one small k (e.g., k=4 or k=5) to make the improvement concrete.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on the verification of the potential-function conditions. We agree that explicit checks are required for the central claims and will incorporate them in the revision.
read point-by-point responses
-
Referee: [Abstract / application to C_k] The headline explicit bound for the C_k game rests entirely on the assertion that the chosen potential function satisfies the C-dependent conditions stated for the general strategy. The abstract invokes this fulfillment but supplies no derivation, inequality checks, or error analysis; this verification step is load-bearing for the central claim and must be exhibited explicitly (with all constants tracked) in the section applying the general theorem to cycles.
Authors: We acknowledge that the current manuscript does not display the full derivation, inequality checks, or constant tracking for the C_k case. In the revised version we will add a new subsection (immediately following the statement of the general theorem) that verifies each C-dependent condition for the chosen potential, with all constants tracked explicitly and the resulting bound derived step-by-step from the general result. revision: yes
-
Referee: [General Breaker strategy] The general strategy is stated to apply only when the potential meets the listed conditions depending on C; without an independent check that these inequalities hold for the specific potential chosen for C_k (including the precise dependence on k), the reduction from the general theorem to the displayed root expression cannot be confirmed.
Authors: We agree that an independent, self-contained verification is necessary. The revision will contain a complete check of every listed inequality for the C_k potential, showing the precise k-dependence and confirming that the displayed (k-1)th-root bound follows directly. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper presents a general Breaker strategy that holds whenever a chosen potential function satisfies a list of C-dependent conditions, then applies the framework to C_k by selecting a potential and verifying those conditions hold, yielding the explicit bias bound. This verification step is an independent calculation within the manuscript rather than a reduction of the output to the input by definition, fitting, or self-citation chain. Asymptotic optimality is supported by the external citation to Bednarska and Łuczak (2000). No equations equate the claimed prediction to a fitted parameter by construction, and the overlapping-author citation to the 2022 potential-method paper is not load-bearing for the central constructive result.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
József Balogh and Wojciech Samotij. On the Chvàtal-Erdős triangle game.Electronic Journal of Combinatorics, 18(1):Research Paper P72, 2011
work page 2011
-
[2]
József Beck. Remarks on positional games. I.Acta Mathematica Academiae Scientiarum Hungaricae, 40(1-2):65–71, March 1982
work page 1982
-
[3]
Random Graphs and Positional Games on the Complete Graph
József Beck. Random Graphs and Positional Games on the Complete Graph. InRandom Graphs ’83, volume 118 ofNorth-Holland Mathe- matics Studies, pages 7–13. North-Holland, 1985. 43
work page 1985
-
[4]
Encyclopedia of Mathematics and its Applications
József Beck.Combinatorial Games: Tic-Tac-Toe Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2008
work page 2008
-
[5]
Małgorzata Bednarska and Tomasz Łuczak. Biased positional games for which random strategies are nearly optimal.Combinatorica, 20:477–488, 2000
work page 2000
-
[6]
Vašek Chvátal and Paul Erdős. Biased Positional Games. InAlgorithmic Aspects of Combinatorics, volume 2 ofAnnals of Discrete Mathematics, pages 221–229. Elsevier, 1978
work page 1978
-
[7]
Maker playing against an invisible Breaker, 2025
Dennis Clemens, Fabian Hamann, Mirjana Mikalački, Yannick Mogge, and Miloš Stojaković. Maker playing against an invisible Breaker, 2025. https://arxiv.org/abs/2507.22519
-
[8]
Heidi Gebauer and Tibor Szabó. Asymptotic random graph intuition for the biased connectivity game.Random Structures & Algorithms, 35(4):431–443, 2009
work page 2009
-
[9]
A new bound for the Maker–Breaker triangle game.European Journal of Combinatorics, 104:103536, 2022
Christian Glazik and Anand Srivastav. A new bound for the Maker–Breaker triangle game.European Journal of Combinatorics, 104:103536, 2022
work page 2022
-
[10]
Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional Games. Springer Basel, 2014
work page 2014
-
[11]
Dan Hefetz, Mirjana Mikalački, and Miloš Stojaković. Doubly Biased Maker-Breaker Connectivity Game.The Electronic Journal of Combi- natorics, 19(1):P61, Mar. 2012. 44
work page 2012
-
[12]
Michael Krivelevich. The critical bias for the Hamiltonicity game is (1+o(1))n/ln n.Journal of the American Mathematical Society, 24(1):125–131, 2011
work page 2011
-
[13]
Eine neue Strategie für den Breaker imC 4-Maker- Breaker-Spiel
Matthias Sowa. Eine neue Strategie für den Breaker imC 4-Maker- Breaker-Spiel. Master’s thesis, Kiel University, 2021
work page 2021
-
[14]
On the Maker-Breaker k-Cycle Game
Matthias Sowa. On the Maker-Breaker k-Cycle Game. PhD thesis, Kiel University, 2026
work page 2026
-
[15]
Matthias Sowa and Anand Srivastav. A Constructive Winning Maker Strategy in the Maker-BreakerC4-Game.Electronic Journal of Combi- natorics, 32(1), 2025
work page 2025
-
[16]
Lokalisierung des Threshold-Bias des Maker-Breaker Sub- graphenspiels
Lena Wolos. Lokalisierung des Threshold-Bias des Maker-Breaker Sub- graphenspiels. Bachelor’s thesis, Kiel University, 2023. 45
work page 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.