Fast Maker Constructions of Regular Graphs

Definitions and mathematical statement

Let $d\geq1$ be an integer and let $G$ be a finite simple $d$-regular target graph. In the usual unbiased Maker--Breaker interpretation of $(K_N,G)$, the players claim previously unclaimed edges of $K_N$, one per move each, and Maker wins when his claimed edges contain a copy of $G$. The copy need not be induced. A round convention typically counts one Maker move together with the corresponding Breaker move. The source does not reproduce its rules, bias, or first-player convention, so these standard rules must be matched before quantitative conclusions are asserted.

The question asks for infinitely many target graphs for each fixed $d$, with a winning-time bound linear in the target order and independent of the sufficiently large board size. A natural uniform formulation is: find $f:{\mathbb{Z}}_{\geq1}\to(0,\infty)$ and, for each $d$, infinitely many pairwise nonisomorphic $d$-regular graphs $G$, such that \[ \forall G\text{ in that family}\quad\exists N_0=N_0(G,d)\quad \forall N\geq N_0, \] Maker has a strategy winning against every legal opponent play within $f(d)|V(G)|$ rounds. The strategies may depend on $G,N$, and the board threshold need not be uniform over all targets. No connectedness of $G$, exact target order, or linear relation between $N$ and $|V(G)|$ is required in the extract.

The requested coefficient satisfies \[ f(d)\leq(1+o(1))d. \] Because the statement fixes $d$ before choosing its graph family but leaves the little-$o$ variable unmarked, the limiting regime needs confirmation. The natural interpretation for a function of $d$ is $d\to\infty$, namely $\limsup_{d\to\infty}f(d)/d\leq1$. A regime in which the error tends to zero with $|V(G)|$ for each fixed $d$ would be a different quantitative statement and is not silently identified with it.

The supplied assessment checked 2026-08-21 identifies this as Problem 3.1 of the report and reports it open as a near-optimal linear-time construction problem. It supplies no exact game-rule definition, asymptotic clarification, or resolving bound.

Short English statement

For every fixed degree, seek infinitely many regular targets that Maker can build in a number of rounds bounded by $f(d)$ times target size on every sufficiently large complete board, with coefficient asymptotically at most $d$. The game rules and little-$o$ regime need confirmation.

Sources

• Local UnsolvedMath registry, permanent ID 30000732, catalogue entry, Fast Maker Constructions of Regular Graphs.
• Mini-Workshop: Positional Games (2008), Oberwolfach Reports, pp. 1073--1114, DOI https://doi.org/10.4171/owr/2007/20, Problem 3.1 as identified in the supplied assessment.
• Supplied literature triage checked 2026-08-21 cites only that report; no separate strategy theorem or precise asymptotic convention is supplied.