The random strategy in Maker-Breaker graph minor games
Pith reviewed 2026-05-24 23:28 UTC · model grok-4.3
The pith
The uniformly random strategy for Maker is essentially optimal with high probability in the H-graph minor game.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove an analogous result for the H-graph minor game to the one Bednarska and Łuczak obtained for the H-subgraph game: the uniformly random strategy for Maker is essentially optimal with high probability. We also study for which choices of H the random strategy is within a factor of 1+o(1) of being optimal.
What carries the argument
The (1:b) Maker-Breaker game in which Maker wins upon claiming a graph that contains H as a minor.
If this is right
- For every fixed H the random Maker strategy wins the minor game against any bias b that is a constant factor below the threshold known from the subgraph case.
- There exist infinite families of H for which the random strategy achieves the optimal threshold up to a 1+o(1) multiplicative factor.
- The minor-game threshold is at most a constant factor larger than the subgraph-game threshold for the same H.
- The result removes the need to design non-random strategies when only the asymptotic order of the bias threshold matters.
Where Pith is reading between the lines
- The same random-strategy analysis may apply to other monotone graph properties that are closed under taking minors.
- If the 1+o(1) optimality holds for all H, then deterministic strategy design becomes unnecessary for any minor-closed winning set.
- The transfer from subgraph to minor may fail for properties that are not minor-closed, suggesting a boundary between the two settings.
Load-bearing premise
The bias thresholds and proof methods that work for the subgraph game carry over to the minor game for the same H without further restrictions on the structure of H.
What would settle it
An explicit graph H together with a bias b where the random Maker strategy loses with high probability while some other strategy wins with high probability, or vice versa, at a scale outside the 1+o(1) window.
Figures
read the original abstract
In a $(1:b)$ biased Maker-Breaker game, how good a strategy is for a player can be measured by the bias range for which its rival can win, choosing an appropriate counterstrategy. Bednarska and {\L}uczak proved that, in the $H$-subgraph game, the uniformly random strategy for Maker is essentially optimal with high probability. Here we prove an analogous result for the $H$-graph minor game, and we study for which choices of $H$ the random strategy is within a factor of $1+o(1)$ of being optimal.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves an analogous result to the Bednarska-Łuczak theorem on the H-subgraph Maker-Breaker game: in the (1:b) H-graph minor game on K_n, the uniformly random strategy for Maker is essentially optimal with high probability. It further characterizes those graphs H for which the random strategy achieves optimality within a (1+o(1)) factor.
Significance. If the results hold, the work extends the analysis of random strategies from subgraph containment to the more general setting of minors, with an explicit H-dependent characterization of near-optimality. This adds a structural perspective to the study of strategy optimality in biased positional games.
minor comments (1)
- The introduction could include a brief reminder of the precise bias threshold from Bednarska-Łuczak to make the analogy self-contained for readers.
Simulated Author's Rebuttal
We thank the referee for the positive report, the assessment of significance, and the recommendation to accept the manuscript. There are no major comments requiring a point-by-point response.
Circularity Check
No significant circularity
full rationale
The paper explicitly cites the independent Bednarska-Łuczak result on the H-subgraph game as the foundation for proving an analogous statement for the H-minor game. No derivation step reduces by construction to a fitted parameter, self-defined quantity, or self-citation chain; the central claim is an extension whose validity rests on the external cited theorem plus new analysis of H-dependence. The provided abstract and reader summary contain no equations or load-bearing steps that collapse to the inputs by definition.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
M. Bednarska and T. Luczak. Biased positional games for which random strategies are nearly optimal. Combinatorica, 20, 2000
work page 2000
-
[2]
M. Bednarska and O. Pikhurko. Biased positional games on matroids. European Journal of Combinatorics , 26, 2005
work page 2005
-
[3]
V. Chv´ atal and P. Erd˝ os. Biased positional games. Annals of Discrete Mathematics, 2, 1978
work page 1978
-
[4]
H. Gebauer and T. Szab´ o. Asymptotic random intuition for the biased connectivity game. Random Structures and Algorithms , 35, 2009
work page 2009
-
[5]
J. Groschwitz and T. Szab´ o. Sharp thresholds for half-random games I. Random Structures and Algorithms , 49, 2016
work page 2016
-
[6]
Y. O. Hamidoune and M. L. Vergnas. A solution to the box game. Discrete Mathematics, 65, 1987
work page 1987
- [7]
-
[8]
M. Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1))n/ lnn. Journal of the American Mathematical Society , 24, 2011
work page 2011
-
[9]
M. Krivelevich. Finding and using expanders in locally sparse graphs.SIAM Journal on Discrete Mathematics , 32:611–623, 2018
work page 2018
-
[10]
M. Krivelevich and G. Kronenberg. Random-player Maker-Breaker games. Electronic Journal of Combinatorics , 22, 2015
work page 2015
- [11]
-
[12]
W. Mader. Subdivisions of a graph of maximal degree n + 1 in graphs of average degree n +ϵ and large girth. Combinatorica, 21, 2001. Ander Lamaison <lamaison@zedat.fu-berlin.de> Institut f¨ ur Mathematik, Freie Univer- sit¨ at Berlin and Berlin Mathematical School, Berlin, Germany. 17
work page 2001
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.