Global Strategies in Irregular Graph-Construction Games

Definitions and mathematical statement

The supplied text is a truncated concluding-remarks question about Maker's time to construct a highly irregular target graph $G$. It asks whether a global strategy, in which Maker postpones choosing which board vertex represents each vertex of $G$, can produce an asymptotically faster construction than local strategies. To identify the distinction without supplying missing game rules, consider conditionally an edge-claiming board graph $B$ and let $M_t$ be the graph of Maker's claimed edges after $t$ of Maker's moves. In the ordinary non-induced-copy interpretation, successful construction at time $t$ means that there exists an injection $\phi:V(G)\to V(B)$ such that \[\{\phi(u),\phi(v)\}\in E(M_t)\qquad\text{for every }\{u,v\}\in E(G).\] A strategy of the kind asked for need not commit to the final injection $\phi$ at the outset; the completed embedding may depend on play. This describes the intended flexibility, but the source gives no formal definition of the competing local strategies or of the permitted postponement. Once a game and a strategy class $\mathcal S$ are specified, its optimal guaranteed construction time can be denoted \[T_{\mathcal S}(B,G)=\inf_{\sigma\in\mathcal S}\sup_{\tau}t_{\mathrm{win}}(\sigma,\tau),\] where $\tau$ ranges over legal opponent strategies and failure to construct has time $+\infty$. The unresolved source question is whether the global strategy class yields an asymptotic improvement over the local class for highly irregular targets. No target family, asymptotic parameter, quantitative irregularity condition, or meaning of improvement is supplied; thus neither a precise ratio bound nor existential versus universal quantification over graph families can be fixed from this fragment. The supplied 2026-08-21 triage labels the record open, expressly calls it a truncated fragment, and says no resolution of the underlying question was found.

Short English statement

Can Maker build irregular target graphs faster by delaying the assignment of target vertices to board vertices? The extract does not give the game rules, the local-strategy benchmark, or the asymptotic regime needed for a quantitative conjecture.

Sources

• Local UnsolvedMath registry, permanent ID 30000733, source problem catalogue entry, Global Strategies in Irregular Graph-Construction 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.