Threshold Bias in the Odd-Cycle Game

Definitions and mathematical statement

For each integer $n\geq 3$, let $K_n$ be the complete simple graph on vertex set $\{1,\ldots,n\}$. An odd cycle is a simple cycle of length $2k+1$, where $k\geq 1$. Define the family of winning edge sets by \[ OC_n=\left\{A\subseteq E(K_n): A\text{ contains every edge of some odd cycle}\right\}. \] In a biased Maker--Breaker odd-cycle game, Maker and Breaker claim previously unclaimed edges of $K_n$; Maker wins by obtaining an edge set in $OC_n$, and Breaker wins if Maker never does so.

The supplied record does not specify the move order, the treatment of an incomplete final move, or the exact threshold convention. An explicit conventional interpretation is the following: Maker moves first and claims one edge per turn; Breaker then claims $b$ edges per turn, or all remaining edges if fewer than $b$ remain. For this interpretation, allow $b\in{\mathbb{Z}}_{\geq 0}$, with $b=0$ an auxiliary convention under which Breaker claims no edges, and define \[ b_{\mathrm{MB}}(OC_n)=\max\left\{b\in{\mathbb{Z}}_{\geq 0}:\text{Maker has a strategy guaranteeing an odd cycle}\right\}. \] These conventions require confirmation against the cited source; they are not explicitly supplied by the registry record.

With $b_{\mathrm{MB}}(OC_n)$ understood as the intended source threshold, the question is whether \[ b_{\mathrm{MB}}(OC_n)=\left(\frac12+o(1)\right)n \qquad\text{as }n\to\infty. \] Equivalently, is it true that for every real $\varepsilon>0$ there exists an integer $N\geq 3$ such that every integer $n\geq N$ satisfies \[ \left|\frac{b_{\mathrm{MB}}(OC_n)}{n}-\frac12\right|<\varepsilon? \] The record labels this problem open; that label is supplied curation rather than an independently verified assertion.

Short English statement

Maker tries to claim all edges of an odd cycle in the complete graph, while Breaker claims $b$ edges for each edge claimed by Maker. The question asks whether the largest bias allowing Maker a guaranteed win is asymptotic to $n/2$. The source's precise play and threshold conventions require confirmation.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003971$, titled Threshold Bias in the Odd-Cycle Game; exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2018 and names no individual proposer. Its corrected_verified statement label and accompanying claim of manual semantic, typographic, and LaTeX review are supplied metadata, not independent mathematical verification.
• Supplied source citation: Mini-Workshop: Positional Games (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/44, pp. 2715--2738. Source URL and literature-source link labelled "OWR report": https://doi.org/10.4171/owr/2018/44. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2019 designation and the record's 2018 proposed year are retained without reconciliation.
• Supplied literature-source link labelled "Odd cycle game": https://doi.org/10.1016/j.ejc.2020.103140. No authors or further bibliographic details are supplied for this reference.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and reports improved lower bounds for the odd-cycle threshold while stating that the proposed asymptotic coefficient $1/2$ has not been established. This is supplied dated curation derived from the supplied OWR curation, not independently verified. The record expressly requests independent verification of time-sensitive status and cited claims; neither linked source has been visited for this draft.