Transition threshold between f and g

Question 4.3 · arXiv:2308.15387

arXiv Question high confidence— first stated 2024-06-10

Authors: Noga Alon, Matija Bucić, Micha Christoph, Michael Krivelevich

Status open high confidence

Question 4.3 asks, for given $n$ and $r$, for the smallest $s$ such that $f(n,r,s)=g(n,r,s)$. The paper separates the functions for $s\ll\sqrt{r}/\log r$ and proves agreement for $s\geq\sqrt{r\log r}$, leaving the crossover open. No follow-up resolving it was found in the May 2026 review.

Reviewer notes. The exact statement was verified in Section 4 of the cached arXiv v2 HTML. The earlier review incorrectly reported that this section was truncated.

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

Question. Given $n$ and $r$, what is the smallest value of $s$ for which $f(n,r,s)=g(n,r,s)$?

Context

After establishing that the functions $f$ and $g$ behave differently for $s\ll\frac{\sqrt{r}}{\log r}$ and similarly when $s\geq\sqrt{r\log r}$, the authors find it interesting to determine precisely when the two functions start to exhibit different behaviour; Question 4.3 is described as an explicit question in this direction.

Source paper

The power of many colours
Noga Alon, Matija Bucić, Micha Christoph, Michael Krivelevich · 2024-06-10
https://arxiv.org/abs/2308.15387