Structure-biased Maker-Breaker Games

Francesca Yu; Wesley Pegden

REVIEW 2 major objections 6 minor 4 references

Structure-biased Maker-Breaker Games

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that in Maker–Breaker games on $K_n$, restricting Breaker's $b$ edges each turn to a clique, matching, or star changes threshold biases by orders of magnitude, with matching and star biases reaching $\Theta(n)$ edges per…

desk verdict New structure-biased games yield real threshold-order results, but the clique-bias connectivity/Hamiltonicity upper bound rests on a lemma that is only sketched. read the letter →

arxiv 2505.21306 v1 pith:6Q3W7AKS submitted 2025-05-27 math.CO

Wesley Pegden , Francesca Yu This is my paper

classification math.CO MSC 05C5791A43

keywords structure-biasedMaker-BreakergamesthresholdbiastrianglegameconnectivityHamiltonicitycliquematchingstar

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a variant of biased Maker–Breaker games in which Breaker's $b$ edges on each turn are required to form (a subgraph of) one fixed structure: a clique, a matching, or a star. It proves that for the triangle, connectivity, and Hamiltonicity games on $K_n$, this structural restriction changes the threshold bias by an order of magnitude: matching and star biases have threshold $b=\Theta(n)$, while clique bias has threshold $m=\Theta(\sqrt n)$ for triangles and $m=\Theta(\sqrt{n/\ln n})$ for connectivity and Hamiltonicity. In terms of edges per turn, Maker can now survive against Breaker taking a constant fraction of the board in the matching and star cases, far above the classical $n/\ln n$ barrier for connectivity and Hamiltonicity. The point of the paper is that fixed-shape Breakers are much weaker than free Breakers, and that this separation identifies which parts of classical Breaker strategies actually matter.

What carries the argument

The load-bearing objects are three. First, a modified Box Game lemma (Lemma 3.4): with $q$ disjoint boxes of size $p$ and Breaker able to delete a box per turn, BoxMaker wins by claiming an $a\times b$ rectangle of perimeter $m$ each turn whenever $(1-2/m)^{2p/m} > 2p/(mq)+1/q$; this is the tool used to prove the clique-bias upper bound for connectivity and Hamiltonicity by having Breaker isolate a vertex. Second, the danger-function and averaging strategy, in which Maker always plays at a vertex of largest danger among active vertices, where danger is $d_B(v)$ or $d_B(v)-2b\,d_M(v)$ depending on the game; this yields the $\Theta(n)$ lower bounds for matching and star biases. Third, the expander-booster machinery: once Maker has built a $k$-expander with minimum degree at least $16$, the graph has $\Theta(k^2)$ available boosters per turn, which is enough to force a Hamilton cycle; this converts the minimum-degree lower bounds into Hamiltonicity thresholds.

What would settle it

Test Lemma 3.4 computationally: choose values of $p$, $q$, and $m$ satisfying $(1-2/m)^{2p/m} > 2p/(mq)+1/q$ and simulate BoxBreaker against the proposed balancing strategy; a single loss for BoxMaker would invalidate the lemma and with it the clique-bias upper bounds for $C(K_m,n)$ and $H(K_m,n)$. As a whole-theorem check, compute the threshold for the clique-biased connectivity game at moderate $n$ and compare the scaling of $m$ against $c\sqrt{n/\ln n}$ for constants $c$ near the paper's bounds.

Watch

Extended reading notes

Core claim

The central discovery is that requiring Breaker to claim edges in a prescribed structure on each move raises threshold biases dramatically and by structure-dependent amounts. Specifically, for the clique bias the threshold biases are $m=\Theta(\sqrt n)$ for the triangle game and $m=\Theta(\sqrt{n/\ln n})$ for connectivity and Hamiltonicity; for matching and star biases, all three games have threshold $b=\Theta(n)$. Thus in the triangle game a Breaker restricted to cliques, matchings, or stars must be allowed $\Theta(n)$ edges per turn to have any winning chance, versus $\Theta(\sqrt n)$ edges in the unrestricted game; in connectivity and Hamiltonicity, matching- and star-restricted Breakers need $\Theta(n)$ edges per turn, versus $n/\ln n$ unrestricted. The paper also notes a consequence for the classical setting: because all three structure-biased triangle games have much larger thresholds than the classical game, the double-star pattern used in the known optimal triangle-game Breaker strategy is essential and cannot be replaced by cliques, matchings, or stars without losing Breaker's win at classical biases.

Load-bearing premise

The clique-bias upper bound for connectivity and Hamiltonicity rests on Lemma 3.4, a modified Box Game lemma asserting that a certain balancing strategy wins whenever the displayed inequality holds; the proof only sketches the balancing argument, and if that strategy loses, the $\Theta(\sqrt{n/\ln n})$ upper bound fails.

Editorial extensions

If this is right

In the triangle game, a Breaker restricted to cliques, matchings, or stars must receive $\Theta(n)$ edges per turn to stop Maker, whereas an unrestricted Breaker can stop Maker with $\Theta(\sqrt n)$ edges; hence the double-star pattern in the classical strategy is load-bearing.
In the connectivity and Hamiltonicity games, a matching- or star-restricted Breaker needs $\Theta(n)$ edges per turn, so Maker can win against a Breaker taking a constant fraction of all edges each move, far above the classical $n/\ln n$ threshold.
For clique bias, connectivity and Hamiltonicity have threshold $m=\Theta(\sqrt{n/\ln n})$, meaning Breaker can still take about $n/\ln n$ edges per turn; the clique restriction alone does not change the order of magnitude for these two games.
In every bias studied, the Hamiltonicity threshold has the same order of magnitude as the connectivity threshold, because isolating a vertex blocks both goals while the same expander-booster strategy builds a Hamilton cycle.
The results differentiate structures: sparse, low-degree structures such as matchings and stars handicap Breaker severely, while dense cliques are comparatively powerful for connectivity-type goals.
Maker beats a Breaker stuck with matchings or stars per turn

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same averaging arguments should extend to any fixed structure of bounded degree, such as paths, cycles, or bounded-degree trees, giving $\Theta(n)$ thresholds for connectivity and Hamiltonicity; the paper's open problems gesture at this wider family.
If Lemma 3.4 could be made tight, it would pin down the constant in the clique-bias connectivity threshold and might transfer to hypergraph versions of the Box Game.
The structure-biased results offer a diagnostic for classical Breaker strategies: any unrestricted Breaker strategy that on every turn uses only edges of one fixed structure cannot beat the corresponding structure-biased threshold, so such a strategy cannot be optimal for connectivity or Hamiltonicity at the classical $n/\ln n$ scale.
On sparser boards such as $G(n,p)$, the $\Theta(n)$ matching and star thresholds should degrade with $p$; testing how the thresholds scale in $p$ would separate edge-count effects from structural effects.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know about arXiv:2505.21306. First, the core idea is a genuinely new variant: Breaker must take his b edges as a subgraph of a prescribed structure on each turn. That twist produces real and sometimes surprising threshold orders — e.g., in the triangle game with clique bias, the threshold clique size is Θ(√n), meaning Breaker is forced to spend Θ(n) edges per move and Maker still survives; the matching- and star-biased thresholds are all Θ(n) edges per move. Second, the paper as written is not fully rigorous: the upper-bound halves of the connectivity and Hamiltonicity clique-bias results (Theorem 1.4(2)(3)) rely entirely on Lemma 3.4, a modified Box Game lemma whose proof is a three-sentence sketch. That is the load-bearing gap.

What the paper does well: it asks a natural question that hasn't been studied, and it identifies a qualitative phenomenon — structure obstructs Breaker. The triangle-game lower bound is a neat counting argument. The matching- and star-bias sections extend Gebauer–Szabó and Krivelevich in a controlled way, and Lemma 5.2 is a clean standalone inequality with a tight bound. The reductions for lower bounds are straightforward applications of classical theorems, which is fine.

The soft spots. Lemma 3.4 is not proved. The 'balancing' strategy is described in a few sentences; no invariant is stated, and the sufficient condition (1−2/m)^{2p/m} > 2p/(mq)+1/q is simply asserted. The application in Theorem 3.3 is equally terse: after Stage 1 it says 'applying the previous lemma renders the desired result' without substituting p=n−|V|, q=|V| or checking the condition for m=Θ(√(n/ln n)). Until that lemma has a complete proof, Theorem 1.4(2) and (3) are open. This is a true gap, not a manufactured one. There are also smaller issues: the 'perimeter m' terminology is off (an a×b rectangle with a+b=m is more like a half-perimeter; the described m/2×m/2 rectangle has a+b=m), some theorems don't specify which player moves first even though that matters (Prop 4.2 vs the b=n/2 Breaker win for even n), and a few typos.

Who gets value from this: researchers in positional games. The variant is worth having in the literature, and the triangle and matching/star results are probably correct as stated. But I would not accept the proof of Theorem 1.4(2)(3) in its current form. My recommendation: send to a serious referee, and ask the authors to fully prove Lemma 3.4 and verify the condition in the applications. If the lemma is repairable — and I suspect it is — this becomes a solid paper.

Referee Report

2 major / 6 minor

Summary. The paper introduces structure-biased Maker-Breaker games on K_n, in which Breaker's b edges per turn must form a subgraph of a prescribed structure. It studies triangle, connectivity, and Hamiltonicity games under three structures: K_m cliques, matchings of size b, and stars with b leaves. The main results assert order-of-magnitude thresholds: for clique bias, m=Θ(√n) for triangles and m=Θ(√(n/ln n)) for connectivity and Hamiltonicity; for matching and star biases, b=Θ(n) for all three games. The proofs use a modified Box Game lemma for the clique upper bounds and adapt Gebauer-Szabó/Krivelevich danger-function methods for the matching and star lower bounds.

Significance. The paper introduces a natural variant that quantifies how structural restrictions on Breaker change the biased positional game. If the results are correct, they show that requiring Breaker to take a clique, matching, or star dramatically increases the threshold bias measured in edges per turn, and they identify structural features, such as the double star in the classical triangle game, that are essential for optimal Breaker strategies. The triangle clique-biased theorem and the matching/star sections are mostly well argued and use established techniques. The main weakness is the unproved modified Box Game lemma on which the clique connectivity/Hamiltonicity upper bounds depend; with that lemma completed, the paper would be a solid contribution.

major comments (2)

[Section 3, Lemma 3.4] The proof of this lemma is not complete. The strategy is described in terms of quantities a_i and b_i, but no invariant is stated that connects these quantities to the number of boxes claimed in a column; the assertion that BoxMaker wins if Σ b_i < q is not derived; and the displayed sufficient condition is asserted without proof. The phrase 'dwell on the ith column with width m/2' is undefined. Because Theorem 3.3 invokes this lemma to prove the Breaker upper bound for C(K_m,n), and the following paragraph extends it to H(K_m,n), Theorems 1.4(2)-(3) are unproved as written. Please supply a complete proof or a precise citation to a result that contains it.
[Section 3, Theorem 3.3, Stage 2] The application of Lemma 3.4 is not verified. The text sets p=n−|V| and q=|V| with q=m^2/16, but Stage 1 constructed a clique on |V|=(m+2)^2/16 vertices; the two expressions should be reconciled. The paper also does not substitute these values into the lemma's condition or check that the condition holds for the stated range m=Θ(√(n/ln n)) with an appropriate constant. A quantitative check is needed, since the lemma's condition depends on m, p, and q.

minor comments (6)

[Section 4, Theorem 4.4] The statement says 'The threshold bias m for the Hamiltonicity game H(E_b,n) is Θ(n)', but the bias variable is b, not m; this should be corrected.
[Section 5, Lemma 5.2] The displayed bound in the statement is garbled: the proof derives a′ − a ≤ c + k − 2 − (c−1)/k, which should be stated cleanly with parentheses.
[Section 5, Theorem 5.1] The stated condition on b appears to be b < (n−1)/2, but the algebra in the proof requires b < (n−2)/2; the statement and proof should be aligned.
[Section 4, Proposition 4.2] For even n, K_n decomposes into n−1 perfect matchings, not n; the sentence about Breaker taking edges 'in his n turns' should be corrected to reflect the correct number of rounds.
[Section 3, Theorem 3.3, Stage 2] The notation |V| is used inconsistently: Stage 1 yields |V|=(m+2)^2/16, while Stage 2 substitutes |V|=m^2/16. Please reconcile the notation and the numerical values.
[Section 3, Theorem 3.2] The end of the Maker-strategy proof refers to 'within m+1 turns' and then to 'Breaker’s (m+2)th turn'; the turn indexing should be clarified to avoid an apparent off-by-one error.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: external classical theorems supply the load-bearing bounds; Lemma 3.4's sketch is a proof gap, not a circular step.

full rationale

No circularity is present in the paper's derivation chain. The lower bounds for the clique-biased connectivity and Hamiltonicity games are inherited from the external classical threshold theorems of Gebauer-Szabó and Krivelevich (Theorems 1.2 and 1.3), and the upper bounds are attempted through a newly stated Box-game lemma (Lemma 3.4), not through assuming the claimed conclusion. The Breaker upper bound for the triangle game imports the classical b >= 2*sqrt(n) result (Theorem 3.1) and then observes that a clique of size m can contain the m/2 edges prescribed by that strategy; this is a valid simulation step, not a circular reduction. None of the paper's central claims is defined in terms of the quantity being predicted, no fitted parameter is relabeled as a prediction, and the cited external results are not by the present authors. The flagged weakness in the paper is Lemma 3.4: its displayed sufficient condition is asserted after only a short sketch, and the proof of Theorem 3.3 does not explicitly verify the lemma's hypotheses when it is applied. That is an omitted proof / correctness risk, not a circular step, so it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data; the constants in the theorems (such as 0.1 and 3/7) are derived from the proofs. No new entities are postulated. The central claims rest on standard background results from the Maker-Breaker literature and on the game definitions.

assumptions (5)

standard math Classical biased Maker-Breaker threshold results (Theorems 1.1, 1.2, 1.3 and Theorem 3.1) are used as black boxes.
The paper's lower and upper bounds for structure-biased games are anchored to these known bounds.
standard math Expander graph facts, including Proposition 4.8 (every component in a k-expander has size at least 3k) and Theorem 4.9 (a connected k-expander has at least (k+1)^2/2 boosters), are taken as folklore.
Used in Stages 2 and 3 of the Hamiltonicity proofs.
standard math Proposition 4.10 from Krivelevich, which asserts that if Maker wins the minimum degree game then she creates a k-expander with high probability, is imported without proof.
This proposition is the core of Stage 1 in the Hamiltonicity proofs for matching and star biases.
domain assumption In the (1:E_b) matching-biased game, Breaker's b edges on a turn must be pairwise disjoint; this is the definition of the game.
The proofs, e.g., Theorem 4.3, rely on Breaker claiming a matching with b disjoint edges.
domain assumption Maker-Breaker game order: Breaker moves first unless otherwise stated; the paper swaps roles or assumes Maker first in some propositions.
The proofs explicitly consider who moves first; this affects thresholds as shown in Proposition 4.2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Structure-biased Maker-Breaker Games." pith.science (2026). https://pith.science/paper/6Q3W7AKS

@misc{pith2026250521306,
  author       = {Pith},
  title        = {Pith review of: Structure-biased Maker-Breaker Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6Q3W7AKS}},
  note         = {Machine review of arXiv:2505.21306}
}

abstract

In classical Maker-Breaker games on graphs, Maker and Breaker take turns claiming edges; Maker's goal is to claim all of some structure (e.g., a spanning tree, Hamilton cycle, etc.), while Breaker aims to stop her. The standard question considered is how powerful a Breaker Maker can defeat; i.e., for the $(1:b)$-biased game where Breaker takes $b$ edges per turn, how large can $b$ be for Maker to still have a winning strategy, for various possible goal sets? We introduce a variant of this question in which Breaker is required to choose their multiple edges as the edges of (a subgraph of) a given structure (e.g., a matching, clique, etc.) on each turn. We establish the order of magnitude of the threshold biases for triangle games, connectivity games, and Hamiltonicity games under clique, matching, and star biases respectively. We conclude that in many cases structure imposes major obstruction to Breaker, opening up a set of games whose strategies deviate from the classical biased Maker-Breaker game strategies, and shedding light on the types of Breaker strategies that may or may not work to prove tighter bounds in the classical setting.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

Asymptotic random graph intuition for the biased connectivity game

Heidi Gebauer and Tibor Szab´ o. Asymptotic random graph intuition for the biased connectivity game. Random Structures and Algorithms , 35 (2009), 431–443

work page 2009
[2]

A new bound for the Maker–Breaker triangle game

Christian Glazik and Anand Srivastav. A new bound for the Maker–Breaker triangle game. European Journal of Combinatorics , 104 (2022), 103536

work page 2022
[3]

Positional Games

Dan Hefetz, Michael Krivelevich, Miloˇ s Stojakovi´ c, and Tibor Szab´ o. Positional Games . Birkh¨ auser, 2014

work page 2014
[4]

The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n

Michael Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n. Journal of the American Mathematical Society , 24 (2011), 125–131. 13

work page 2011

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Asymptotic random graph intuition for the biased connectivity game

Heidi Gebauer and Tibor Szab´ o. Asymptotic random graph intuition for the biased connectivity game. Random Structures and Algorithms , 35 (2009), 431–443

work page 2009

[2] [2]

A new bound for the Maker–Breaker triangle game

Christian Glazik and Anand Srivastav. A new bound for the Maker–Breaker triangle game. European Journal of Combinatorics , 104 (2022), 103536

work page 2022

[3] [3]

Positional Games

Dan Hefetz, Michael Krivelevich, Miloˇ s Stojakovi´ c, and Tibor Szab´ o. Positional Games . Birkh¨ auser, 2014

work page 2014

[4] [4]

The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n

Michael Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n. Journal of the American Mathematical Society , 24 (2011), 125–131. 13

work page 2011