Move Complexity and Surplus in Maker Games

Definitions and mathematical statement

The record combines three questions. Let $K_\infty$ denote the complete graph on a countably infinite vertex set, and write $R_M(G)$ for the source's minimum number of moves in which Maker can force a copy of a finite target graph $G$; put $R_M(n)=R_M(K_n)$. In the usual edge-claiming interpretation, a copy is an injective vertex map carrying each target edge to an edge claimed by Maker. A guaranteed time takes a minimum over Maker strategies and a worst case over legal opponent strategies. The source does not specify the move rules, player order, or whether moves count Maker turns or both players' turns.

1. The supplied bounds are \[2^{n/2}\leq R_M(n)\leq C2^n.\] Can their gap be closed or reduced? The source gives no particular proposed sharper function or explicit range of $n$ for the displayed bounds.
2. For a $d$-regular graph $G$ on $n$ vertices, is there a universal constant $c>1$ such that \[R_M(G)\geq c^d n\] for every such $G$ in the intended parameter range? The universal constant in this question need not be the constant $C$ in the first bound. The degree range and move normalization require clarification: for instance, with single-edge Maker moves on $K_\infty$, a matching on $n$ vertices can be claimed using $n/2$ Maker moves, so the literal inclusion of all $1$-regular graphs is incompatible with the proposed inequality. No missing degree restriction or multiplicative prefactor is silently inserted.
3. In a Maker--Breaker game on the cells of an $n\times n^2$ grid, can Breaker's trivial upper bound on Maker's surplus in a row or column be improved, and is the correct order $\Theta(\sqrt{n\log n})$? Here the record is internally inconsistent: the original statement gives the trivial upper bound as $\sqrt n$, whereas the clean and current statements give it as $n$. A nonnegative quantity bounded above by $\sqrt n$ cannot simultaneously have order $\Theta(\sqrt{n\log n})$ as $n\to\infty$. Both versions are retained for review. The source does not define the surplus or its optimization/time convention. A common signed count for a line $L$ would be $|M\cap L|-|B\cap L|$, with $M,B$ the claimed cells, but whether this is maximized over lines, over intermediate times, or in a minimax or random-player model is not supplied.

The supplied literature triage, dated 2026-08-21, labels the record open and says the bounds gap and proposed asymptotics for a random-player quantity remain unresolved. That random-player quantity is not defined in the displayed statements, so this qualification does not determine the missing model.

Short English statement

The record asks about clique construction time, an exponential-in-degree lower bound for regular targets, and grid surplus. The two source versions disagree on the grid's trivial bound ($\sqrt n$ versus $n$), and the regular-graph question needs a degree range and move convention.

Sources

• Local UnsolvedMath registry, permanent ID 30000747, source problem catalogue entry, Move Complexity and Surplus in Maker Games, proposed year 2007; no individual proposer supplied.
• Supplied citation: Mini-Workshop: Positional Games (2008), Oberwolfach Reports, DOI 10.4171/owr/2007/20, pp. 1073--1114: https://doi.org/10.4171/owr/2007/20. Supplied literature label: original Oberwolfach report.