Diagonal and off-diagonal online random Ramsey growth rates

Conjecture 7 · arXiv:1806.09726

arXiv Conjecture high confidence— first stated 2018-11-04

Authors: David Conlon, Jacob Fox, Andrey Grinshpun, Xiaoyu He

Status open medium confidence

Conjecture 7 from arXiv:1806.09726 posits that the diagonal online random Ramsey numbers grow as $2^{(1+o(1))\frac{2}{3}n}$ and the off-diagonal as $n^{(1+o(1))\frac{2}{3}m}$. The conjecture is tied to the Subgraph Query Problem via Theorem 10 and Conjecture 9 of the same paper. A 2019 follow-up (arXiv:1911.04413) makes progress on the Subgraph Query Problem itself, but a web search through 2026 found no paper that directly resolves either part of Conjecture 7. The conjecture remains open as far as indexed literature reveals.

Cited literature (1)

partial On the subgraph query problem (2019)

Ryan Alweiss, Chady Ben Hamida, Xiaoyu He, Alexander Moreira · arXiv preprint · arXiv:1911.04413

Improves bounds on the Subgraph Query Problem for cliques and degenerate graphs, directly related to the mechanism through which Conjecture 7 is expected to follow, but does not resolve the conjecture's stated growth-rate claims.

Reviewer notes. Semantic Scholar citation list for arXiv:1806.09726 shows no citing paper that directly resolves Conjecture 7. The related paper arXiv:1911.04413 (with Xiaoyu He as co-author of both) works on the subgraph query problem but does not establish the conjectured exponents for r_rand. The conjecture is 8 years old; medium confidence rather than high is assigned because the conjecture's age and its tight connection to an active research topic leave room for a resolution in the literature that was not surfaced by the search.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. (a) The diagonal online random Ramsey numbers satisfy $$\tilde{r}_{rand}(n, n) = 2^{(1+o(1)) \frac{2}{3} n}.$$ (b) The off-diagonal online random Ramsey numbers ($m \geq 3$ fixed and $n \to \infty$) satisfy $$\tilde{r}_{rand}(m, n) = n^{(1+o(1)) \frac{2}{3} m}.$$

Context

The authors define the online random Ramsey number $\tilde{r}_{rand}(m,n)$ as the maximum over $p \in (0,1)$ of $\tilde{r}(m,n;p)$, where Painter independently colors each edge red with probability $p$. These conjectures on the growth rate are motivated by a connection with the Subgraph Query Problem; Theorem 10 and Conjecture 9 together imply both parts of this conjecture.

Source paper

Online Ramsey Numbers and the Subgraph Query Problem
David Conlon, Jacob Fox, Andrey Grinshpun, Xiaoyu He · 2018-11-04
https://arxiv.org/abs/1806.09726 PDF source