Critical Biases in Positional Graph Games

Definitions and mathematical statement

Consider positional games on $E(K_n)$. In the usual $(1:b)$ Maker--Breaker convention, Maker claims one previously unclaimed edge and Breaker claims $b$ per turn; Maker seeks a spanning subgraph with a specified increasing property, and Breaker seeks to prevent this. Turn order, exact versus at-most quotas, and the treatment of an incomplete final turn are not stated in the record and must be fixed.

For any fixed such convention, write \[ b_{\mathrm{MB}}(n,\mathcal P)=\max\{b\geq1:\text{Maker has a winning strategy for }\mathcal P\}, \] when this is the intended monotone critical-bias convention, with zero used if the set is empty. The source asks to close the remaining gap for the Hamilton-cycle bias $b_{\mathrm{MB}}(n,\mathrm{Ham})$, to determine the perfect-matching bias $b_{\mathrm{MB}}(n,\mathrm{PM})$, and to determine the bias $b_{\mathrm{MB}}(n,\mathrm{Conn}_k)$ for $k$-vertex-connectivity. Here a Hamilton cycle visits every vertex, a perfect matching covers every vertex and requires even $n$, and a graph is $k$-vertex-connected if it has more than $k$ vertices and remains connected after deletion of any fewer than $k$ vertices. Whether $k$ is fixed or varies with $n$, and whether exact values or asymptotic precision are required, are unspecified. No numerical endpoints for the stated Hamiltonicity gap are supplied.

In the corresponding Avoider--Enforcer game, Avoider claims one edge per turn and Enforcer claims $b$, with Enforcer seeking to force Avoider's own graph to contain a Hamilton cycle. Let \[ W_{\mathrm{AE}}(n)=\{b\geq1:\text{Enforcer has a winning Hamiltonicity strategy}\}. \] The source asks both to determine the threshold bias and to decide whether such a threshold exists at all. In a strict-bias convention, describing the winning set by a single cutoff is itself an issue; no monotonicity of $W_{\mathrm{AE}}(n)$ is assumed here. The exact sense of threshold, as opposed to separate upper and lower critical biases or an asymptotic transition, needs specification.

The original statement additionally records the question whether Enforcer of bias $(1-o(1))n/\log n$ can force Avoider of bias one to build a Hamilton cycle, and says this particular question was subsequently resolved affirmatively. The unspecified $o(1)$ and integer rounding are retained as an asymptotic source formulation, without upgrading it to a claim for every such bias sequence. The dated assessment checked 2026-08-21 likewise reports this asymptotic resolution, but labels the bundled record partially solved because it retains the other threshold and matching questions. This reported answer does not settle every item in the bundle.

Short English statement

Determine the Hamilton-cycle, perfect-matching and connectivity critical biases for Maker--Breaker games, and determine whether a Hamiltonicity cutoff exists for Avoider--Enforcer games. Preserve the source's reported affirmative answer to its separate Enforcer-bias $(1-o(1))n/\log n$ question.

Sources

• Local UnsolvedMath registry, permanent ID 30000900, source code catalogue entry; supplied complete record, including its longer original statement, corrected-verified source-check note and dated partial-solution assessment.
• Combinatorics (2008), Oberwolfach Reports, DOI 10.4171/owr/2008/01, pp. 5--78: https://doi.org/10.4171/owr/2008/01.
• Krivelevich--Szabo, Avoider--Enforcer: https://www.cs.tau.ac.il/~krivelev/thinning.pdf.
• Hefetz--Krivelevich--Stojakovic--Szabo: https://doi.org/10.1016/j.jcta.2009.05.001.