REVIEW 2 major objections 4 minor 9 references
Maker-Breaker games on infinite graphs with precolored edges
T0 review · 2 major / 4 minor · reviewed 2026-08-28 · deepseek-v4-flash
Pith's one-line read The paper proves a quantitative threshold for winning infinite Maker-Breaker games on precolored edges, and completely solves the two-color case.
desk verdict Strong framework and a clean two-color theorem, but the printed Maker-side bounds in Theorems 1.3–1.5 are not supported by the proof as written; Theorem 4.9's constant needs a repair. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing construction is the reduction of the infinite game to the finite auxiliary game $\operatorname{MB}_{\mathrm{fin}}(C,s,t)$, played on the complete $s$-partite graph $K^s_C$ (a vertex set split into $s$ classes of size $C$): its hyperedges are the $s$-sets of pairwise crossing edges, and Maker must claim an edge set $H$ such that every coloring of the hypergraph $K^{(s)}_C(H)$ admits a color class where Maker wins one of two auxiliary vertex-claiming games. Theorems 4.5 and 4.6 prove the equivalence between this finite game and the infinite game $\operatorname{MB}_{1.4}(C,s,t)$. Inside that proof, the engine is the wish function: Maker grows a finitely branching tree whose comparability graph she claims, attaching fresh vertices whose colors satisfy the wishes of leaves, and she extracts an infinite ray from the tree; the ray's vertices then induce an infinite clique with the prescribed ascending color pattern. Breaker's wins rely on a pairing strategy over the bounded part of the board, built from a proper edge-coloring of the square of the line graph, combined with the classical threshold for the finite clique game.
What would settle it
Compute the winner of $\operatorname{MB}_{\mathrm{fin}}(C,s,t)$ for small parameters and search for a coloring of $K_{\aleph_0}$ at those parameters where the loser of the finite game wins the infinite game; any such pair refutes Theorem 4.5 or Theorem 4.6. Alternatively, construct an edge-coloring of $K_{\aleph_0}$ in which both color classes have infinite maximum degree but Breaker still prevents Maker from obtaining an infinite clique containing both colors infinitely often, which would refute Theorem 1.1.
Extended reading notes
Core claim
The central claim, Theorem 1.5, is a dichotomy for the color-preserving game on $K_{\aleph_0}$ with $s$ graphs of finite order $C_1,\dots,C_s$ (each has exactly $C_i$ vertices of infinite degree, and bounded degree after deleting them) together with $t$ ascending graphs (containing vertices of arbitrarily large degree). If every $C_i$ is at least $\max\{2^t\cdot 2^{(1+o_s(1))3^s},\, 2^{2(1+o_s(1))s}\}$, Maker has a winning strategy. If, for some nonempty $A\subseteq[s]$, $\sum_{j\in A} C_j \le \frac{m(A)}{e} 2^{m(A)/2-1}$, where $m(A)$ is the minimum size of a vertex set meeting all vertices of infinite degree of the graphs in $A$, then Breaker has a winning strategy, and moreover his strategy forces the union of those graphs inside any infinite clique Maker claims to have order strictly less than $m(A)$. The two-color case, Theorem 1.1, is fully decided: Breaker wins exactly when one color class has finite maximum degree, otherwise Maker wins. In the partially pattern-preserving game, Theorem 1.3 shows the minimal number of pairwise disjoint copies of the infinite star $S_{\aleph_0}$ needed per color to force containment of $\ell$ stars from each of $k$ colors satisfies $2^{(1-o(1))k\ell/2}< f^{S_{\aleph_0}}_{\mathrm{par}}(k,\ell) \le 2^{2(1+o(1))k\ell}$.
Load-bearing premise
Maker's thresholds all flow through the equivalence between the infinite structure-preserving game and the finite auxiliary hypergraph game $\operatorname{MB}_{\mathrm{fin}}(C,s,t)$; if a win in the finite game did not transfer to the infinite game (or the transfer in the other direction failed), the Maker-side bounds of Theorem 1.5 would collapse.
Editorial extensions
If this is right
- For any 2-coloring of the edges of $K_{\aleph_0}$, the winner is decided purely by whether both color classes have unbounded maximum degree: Maker wins if both are unbounded, and Breaker wins if one is bounded.
- For several prescribed subgraphs, Maker wins whenever all orders of the non-ascending graphs lie above roughly $2^{2s(1+o_s(1))}$, yielding an explicit doubly exponential sufficient condition.
- Breaker wins whenever a nonempty subfamily has total order at most $(m(A)/e)2^{m(A)/2-1}$, and his strategy bounds the order of the union of those graphs inside any infinite clique Maker can claim.
- The minimum number of disjoint infinite stars needed per color to force $\ell$ preserved stars from $k$ colors lies strictly between $2^{(1-o(1))k\ell/2}$ and $2^{2(1+o(1))k\ell}$.
Reading between the lines
- The doubly exponential gap between the Maker and Breaker thresholds suggests the true critical quantity is $m(A)$, the number of independent infinite-degree hubs, with the exponential in $m(A)$ dominating; pinning the constant would settle the three-or-more-color case.
- The finite-hypergraph reduction is likely reusable: any infinite positional game whose winning condition is an ascending pattern along tree paths might reduce to a finite auxiliary game by the same comparability-tree construction.
- A testable next step from the paper's own open problems is the three-color game where one color class is one or two disjoint infinite stars and another is ascending; the methods here determine it in many cases but leave a boundary case open.
Formalized claims in Lean
-
Claim #1: The central claim, Theorem 1.5, is a dichotomy for the color-preserving game on $K_{\aleph_0}$ with $s$ graphs of finite order $C_1,\dots,C_s$ (each has exactly $C_i$ vertices of infinite degree, and bounded degree after deleting them) together with $t$ ascending graphs (containing vertices of arbitrarily large degree). If every $C_i$ is at least $\max\{2^t\cdot 2^{(1+o_s(1))3^s},\, 2^{2(1+o_s(1))
/-- @claim 1 The central claim, Theorem 1.5, is a dichotomy for the color-preserving game on $K_{\aleph_0}$ with $s$ graphs of finite order $C_1,\dots,C_s$ (each has exactly $C_i$ vertices of infinite degree, and bounded degree after deleting them) together with $t$ ascending graphs (containing vertices of arbitrarily large degree). If every $C_i$ is at least $\max\{2^t\cdot 2^{(1+o_s(1))3^s},\, 2^{2(1+o_s(1)) -/ def central_claim : Prop :=
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Maker-Breaker games on the countably infinite complete graph K_aleph0, where Maker must claim a K_aleph0 with prescribed intersection properties relative to finitely many given subgraphs G_i. The games considered are the color-preserving game MBcol, the pattern-preserving game MBpat, and a partially pattern-preserving variant MBH_par. The main claims are: a complete two-color characterization (Theorem 1.1); bounds on the minimal number of disjoint stars needed for Maker to preserve stars, f^{S_aleph0}_par (Theorem 1.3); a general Maker sufficient condition obtained through a finite auxiliary game MBfin and an infinite-game equivalence (Theorems 1.4, 4.5, 4.6, 4.9); and a combined sufficient/necessary condition for MBcol (Theorem 1.5). The proof technique combines a wish-function construction (Section 3), a reduction to a finite hypergraph game (Section 4), Beck's threshold criterion, and a pairing strategy for Breaker using a bounded-degree edge-coloring (Section 5).
Significance. If the quantitative claims are correct, the paper makes a substantial contribution: the two-color characterization fully resolves the k=2 case of the precolored-edge question from [4], and the finite/infinite equivalence in Theorems 4.5 and 4.6 provides a concrete method for transferring finite hypergraph strategies to infinite games. The paper is largely self-contained and includes a complete proof of the wish-function theorem (Theorem 3.5), which is a strength. The Breaker-side structural guarantee in Theorem 1.5 and the explicit lower bound in Theorem 1.3 are also concrete and checkable. However, the numerical thresholds on the Maker side are not supported by the displayed proofs: the constant in Theorem 4.9 is too small for the Beck inequality used, and the asymptotic upper bounds in Theorems 1.3 and 1.5 do not follow from the application of Theorem 1.4 as written.
major comments (2)
- [§4.9 (proof of Theorem 4.9)] The displayed inequality used to apply Theorem 4.7, namely `2^{s-4} C^{s-3} C(s-1) < C^{s-1}/2^s - C^{s-2}`, is equivalent to `C > (s-1) 2^{2s-4} + 2^s`. The stated constant `C = ceil{s^2 2^{s-3}}` fails this inequality for every s >= 2 (for example, s=4 requires C > 64 while the statement gives C=32), and the s=1 case is degenerate for the (s-1)-uniform Beck criterion. Consequently the proof of Maker's winning strategy in MB_fin(C',s,0), and hence the t=0 case of Theorem 1.4, is invalid as written. The local inequality would hold if the first term were `s^2 2^{2s-3}`, but that is not the stated constant.
- [§5, Lemma 5.1 and proof of Theorem 1.3] Equation (2) in the proof of Theorem 1.3 asserts `f^{S_aleph0}_par(s,1) <= 2^{2(1+o(1))s}` as a consequence of Theorem 1.4 with t=0. However, Theorem 1.4 requires `C' >= 3C(s+1)C^{s+1}`, and with any C of order `2^{Theta(s)}` (whether the stated `s^2 2^{s-3}` or a corrected `s^2 2^{2s-3}`) this gives `C' = 2^{Theta(s^2)}`. The proof displays no argument reducing this to `2^{2(1+o(1))s}`. Since Lemma 5.1 and the Maker-side threshold of Theorem 1.5 are obtained by the same application of Theorem 1.4, the quantitative Maker side of Theorems 1.3 and 1.5 is not established as stated. The qualitative claim that sufficiently large orders suffice may survive a repair, but the printed exponents do not follow from the supplied proof.
minor comments (4)
- [Definition 4.4] The game MB_fin(C,s,t) is defined by saying Maker 'can claim an edge set H' with a certain property, but no stopping rule is stated; since the board is finite, the intended meaning is that the game ends when all edges of E(K^s_C) are claimed, and this should be made explicit.
- [Lemma 3.3] The objects `eG_i_j` are used before being formally defined; please define the disjoint-union components explicitly or replace them with a cleaner notation.
- [Lemma 5.1] The displayed definition `C' := min{C1_s,...,Cs_s}` is garbled by typesetting; please clarify whether the intended quantity is `min_i floor(C_i/s)` or another expression.
- [Theorem 1.5] The condition `C_1,...,C_s >= max{2t * 2^{(1+o_s(1))3s}, 2^{2(1+o_s(1))s}}` uses `o_s(1)` without stating the uniformity in t; please specify the intended asymptotic regime (e.g., s to infinity with t arbitrary).
Circularity Check
No significant circularity: all load-bearing tools are proved in-line or cited as standard external results; the Theorem 4.9 constant discrepancy is a correctness gap, not circularity.
full rationale
This paper proves an infinite Maker–Breaker characterization (Theorem 1.5) and a partially pattern-preserving game result (Theorem 1.4) whose Maker half flows through an explicitly proved equivalence between the infinite game MB_1.4(C,s,t) (Definition 4.1) and the auxiliary finite game MB_fin(C,s,t) (Definition 4.4). The two games are defined independently, and Theorems 4.5 and 4.6 give genuine strategies in both directions (Maker's recursive tree construction with an ascending color pattern; Breaker's transfer of his finite hypergraph-vertex claims, including the pairing step for the star case). No parameter is fitted to any target result: the paper is a pure strategy-existence paper, so the 'fitted input called prediction' pattern does not arise. The only self-citations ([4] and [5]; [1] is a bachelor's thesis at the authors' university) are contextual: the load-bearing wish-function theorem (Theorem 3.5) is proved in full within Section 3, with the proof attributed to Arlt's thesis [1], so the citation to [4] is not needed for the derivation. No uniqueness theorem, ansatz, or rescaling is imported from the authors' prior work. The externally cited results — Beck's criterion (Theorem 4.7, [3, Theorem 2.4]), the finite Ramsey-game bound (Lemma 5.3, [7, Theorem 2.4.1]), and the bounded-degree coloring bound (Lemma 5.4, [6]) — are standard theorems with stated assumptions that do not include the paper's target results, hence constitute real independent support. A reviewer-flagged quantitative discrepancy exists in Theorem 4.9: the displayed inequality 2^(s−4)·C^(s−3)·C(s−1) < C^(s−1)/2^s − C^(s−2) is equivalent to C > (s−1)·2^(2s−4) + 2^s, which the stated bound ⌈s²·2^(s−3)⌉ does not imply (for t=0, s=4: 32 < 64). This is an arithmetically checkable proof gap that propagates to the constants in Theorems 1.4, Lemma 5.1 and the Maker half of Theorem 1.5, and it should be reported as a correctness risk under the current constants. It is not, however, a circularity: no claim in the paper is equivalent by construction to its own input or to a self-citation. The qualitative existence statements plausibly survive a constant repair (the Breaker half, Lemma 5.5, and the two-color characterization, Theorem 1.1, are unaffected). Verdict: no significant circularity; score 2 reflects only the presence of minor, non-load-bearing self-citations.
Assumptions & free parameters
free parameters (5)
- C =
max{ceil(s^2 * 2^{s-3}), 2^{3s+1} * t}
- C' =
3C*(s+1)*C^{s+1}
- tau =
s+3t+1
- alpha =
(3Cs+4)*(s+t)
- Maker threshold in Theorem 1.5 =
max{2^{t*2^{(1+o_s(1))3s}}, 2^{2(1+o_s(1))s}}
assumptions (5)
- standard math Koenig's infinity lemma: every infinite finitely branching rooted tree contains a rooted ray.
- standard math Ramsey's theorem for edge 2-colorings of K_aleph_0.
- standard math Every bounded-degree infinite graph is (Delta+1)-colorable (Brooks-type bound, Lemma 5.4).
- standard math Beck's hypergraph criterion (Theorem 4.7): if |E(F)| > 2^{s-3} * Delta_2(F) * |V(F)| then Maker wins MB_aux^(1)(F).
- standard math Breaker wins the finite Ramsey game MB(n,q) when n <= (q/e) * 2^{q/2 - 1} (Lemma 5.3).
Cite this review
Pith. "Pith review of Maker-Breaker games on infinite graphs with precolored edges." pith.science (2026). https://pith.science/paper/K6OFMIDZ
@misc{pith2026260823349,
author = {Pith},
title = {Pith review of: Maker-Breaker games on infinite graphs with precolored edges},
year = {2026},
howpublished = {\url{https://pith.science/paper/K6OFMIDZ}},
note = {Machine review of arXiv:2608.23349}
}
abstract
Suppose we are given graphs $B$ and $G$. In the classical Maker-Breaker game $\text{MB}(B,G)$ two players, Maker and Breaker, alternately claim edges of $B$ and it is Maker's goal to claim a copy of $G$ in $B$, while it is Breaker's goal to prevent that. In this paper, $B$ is the countably infinite complete graph $K_{\aleph_0}$ and we are given finitely many infinite subgraphs $G_1, \dots, G_k \subseteq B$. In the color preserving game, it will be Maker's goal to claim a $K_{\aleph_0} \subseteq B$, which contains infinitely many edges of each $G_i$. We present sufficient winning conditions for both Maker and Breaker, if $k > 1$ and a full characterization of the game, if $k =1$. This partly answers a question of Bowler, Emde and Gut. In the (partially) pattern preserving game, it is Maker's goal to claim a copy $K$ of $K_{\aleph_0}$, such that $G_i \cap K$ is isomorphic to (a subgraph of) $G_i$ for all $i \in [k]$. In those games, we investigate some patterns for which Maker has a winning strategy.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[4]
The Kℵ0 game: Vertex colouring
Nathan Bowler, Marit Emde, and Florian Gut. “The Kℵ0 game: Vertex colouring”. In: Mathematika 69.3 (Apr. 2023), pp. 584–599.issn: 2041-7942. doi: 10.1112/mtk.12196. url: http://dx.doi.org/10.1112/mtk.12196
-
[1]
Intuitivere Argumente f¨ ur Maker-Breaker-Spiele
Luca Arlt. “Intuitivere Argumente f¨ ur Maker-Breaker-Spiele”. Bachelor’s thesis. Ham- burg: University of Hamburg, July 2024. 26 REFERENCES
work page 2024
-
[2]
J´ ozsef Beck.Combinatorial games . Vol. 114. Encyclopedia of Mathematics and its Applications. Tic-tac-toe theory. Cambridge University Press, Cambridge, 2008, pp. xiv+732. isbn: 978-0-521-46100-9. doi: 10.1017/CBO9780511735202. url: https: //doi.org/10.1017/CBO9780511735202
-
[3]
J´ ozsef Beck. “Ramsey games”. In: vol. 249. 1-3. Combinatorics, graph theory and computing (Louisville, KY, 1999). 2002, pp. 3–30. doi: 10.1016/S0012-365X(01) 00224-2. url: https://doi.org/10.1016/S0012-365X(01)00224-2
-
[5]
Nathan Bowler and Florian Gut. “The Rational Number Game”. In: The Electronic Journal of Combinatorics 31.4 (Dec. 2024). issn: 1077-8926. doi: 10.37236/12380. url: http://dx.doi.org/10.37236/12380
-
[6]
Reinhard Diestel. Graph theory. Sixth. Vol. 173. Graduate Texts in Mathematics. Springer, Berlin, 2025, pp. xx+454. isbn: 978-3-662-70106-5; 978-3-662-70107-2
work page 2025
-
[7]
Dan Hefetz et al.Positional games. Vol. 44. Oberwolfach Seminars. Birkh¨ auser/Springer, Basel, 2014, pp. x+146. isbn: 978-3-0348-0824-8; 978-3-0348-0825-5
work page 2014
-
[8]
¨Uber eine Schlussweise aus dem Endlichen ins Unendliche
D´ enes K˝ onig. “¨Uber eine Schlussweise aus dem Endlichen ins Unendliche”. German. In: Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum 3 (1927), pp. 121–130
work page 1927
Show all 9 references
-
[9]
On a Problem of Formal Logic
F. P. Ramsey. “On a Problem of Formal Logic”. In: Proc. London Math. Soc. (2) 30.4 (1929), pp. 264–286. issn: 0024-6115. doi: 10.1112/plms/s2-30.1.264 . url: https://doi.org/10.1112/plms/s2-30.1.264. Email address : nathan.bowler@uni-hamburg.de, henri.ortmueller@unifr.ch
1929 doi
Reviewed August 28, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.