Asymptotics of Online Random Ramsey Numbers

Definitions and mathematical statement

Let $m,n$ be positive integers. The supplied record uses $\widetilde r_{\mathrm{rand}}(m,n)$ for the online random Ramsey number, but does not define its underlying random process, permitted strategies, stopping rule, or success criterion. Thus the statements below preserve the supplied conjectures; a complete mathematical definition of this parameter remains necessary.

The diagonal conjecture is \[ \widetilde r_{\mathrm{rand}}(n,n)=2^{(1+o(1))(2/3)n} \qquad(n\to\infty). \] The off-diagonal conjecture is that, for every fixed integer $m\geq3$, \[ \widetilde r_{\mathrm{rand}}(m,n)=n^{(1+o(1))(2/3)m} \qquad(n\to\infty). \] Here $n$ tends to infinity through integers, and each occurrence of $o(1)$ denotes an error tending to zero in that limit. In the off-diagonal statement the error may depend on the fixed integer $m$; no uniformity in $m$ is asserted. These are conjectural asymptotics in the supplied record, whose open-status label is not independently verified.

Short English statement

The conjectures predict exponential growth with exponent asymptotic to $2n/3$ on the diagonal, and polynomial growth with exponent asymptotic to $2m/3$ for each fixed integer $m\geq3$. The source record omits the precise definition of the online random Ramsey number, so the intended random model and success criterion require review.

Sources

• Local UnsolvedMath registry: data/unsolvedmath/problems.json, permanent ID $30004123$, source code catalogue entry, title: Asymptotics of Online Random Ramsey Numbers. The supplied record lists proposed year 2019 and names no individual proposer.
• Supplied report citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, pp. 1113--1189, DOI 10.4171/owr/2019/19. https://doi.org/10.4171/owr/2019/19. Also listed as Oberwolfach Report 19/2019; the record describes these reports as documenting mathematical workshops and their open-problem discussions.
• Conlon--Fox--Grinshpun--He, Online Ramsey numbers and the subgraph query problem. https://arxiv.org/abs/1806.09726. This is supplied paper attribution, not an attribution of the problem's proposer.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that both asymptotics are conjectures in the primary paper, whose results give lower bounds rather than matching asymptotics. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; time-sensitive status and cited claims require independent verification.