Loss Thresholds in Two-Round Random Edge Coloring

Definitions and mathematical statement

Consider the source's two-round random edge-coloring game on $n$ vertices. First the entire graph $G(n,p)$ is revealed and its edges are colored offline. Then $N$ additional random edges are revealed and colored online, with each color decision made when the edge is revealed. The number of colors and forbidden configuration defining a loss are not supplied, so no particular Ramsey-avoidance game is silently chosen.

The proposed implication is: for every $\alpha\in[0,1/6]$, if \[ p=\Omega(n^{-1/2-\alpha}),\qquad N=\omega(n^{8\alpha}), \] then the player loses. For a fixed $\alpha$, the first condition means there are $c>0$ and $n_0$ such that $p(n)\ge c n^{-1/2-\alpha}$ for all $n\ge n_0$; the second means $N(n)/n^{8\alpha}\to\infty$. Both endpoints of the stated interval are retained. A varying sequence $\alpha(n)$ is not asserted without source confirmation.

In a usual random-game threshold interpretation, the conclusion would say that every admissible strategy has loss probability tending to one, or that the optimal success probability tends to zero. The source does not state the probability quantifier, its uniformity over strategies, whether strategies may be randomized, or what information is available during the offline round. A single deterministic inevitable-loss assertion is not inferred from asymptotic notation alone.

The distribution of additional edges is also missing: sampling previously absent edges without replacement, independent sampling with repeats, and other models differ. Any feasibility condition on $N$, colors, recoloring rules, or stopping time must be recovered from the report. The exact exponents $-1/2-\alpha$ and $8\alpha$ are preserved, but the incomplete game rules prevent a self-contained theorem of loss.

Short English statement

The source proposes a loss threshold across the full interval $0\le\alpha\le1/6$ after an offline random-graph coloring round and an online extension. The powers of $n$ are explicit, but colors, the losing pattern, edge sampling, and the probabilistic strategy quantifier are missing.

Sources

• Local UnsolvedMath registry, permanent ID 30000745, code catalogue entry, "Loss Thresholds in Two-Round Random Edge Coloring." Proposed year 2007; proposer unspecified.
• Mini-Workshop: Positional Games (2008), Oberwolfach Reports, pp. 1073--1114, DOI 10.4171/owr/2007/20; https://doi.org/10.4171/owr/2007/20. The displayed report year 2008 differs from the DOI and proposed year 2007. This is the sole supplied literature reference.
• Statement status corrected_verified; the supplied note says official-report content was checked and notation, context, and question form normalized without changing the claim.
• Literature triage checked 2026-08-21: open. It says the asymptotic implication is posed as a question and no later resolving theorem was located in the supplied search. No omitted game rule is provided. Created 2026-08-25; updated 2026-09-16. Current status and source scope require independent verification.
• Registry curation by Ulam AI / UnsolvedMath Contributors, CC BY 4.0; the underlying report retains its supplied provenance. Unreviewed statement-only draft.