Precise asymptotic of f(n,r,s) for s ≤ √r/log r
Conjecture 4.2 · arXiv:2308.15387
Status open high confidence
Conjecture 4.2 from arXiv:2308.15387 posits the precise asymptotic $f(n,r,s)=\frac{s^{2}(\log r)^{1-o_{r}(1)}}{r}\cdot n$ in the regime $1\leq s\leq\sqrt{r}/\log r$; the paper itself only establishes this up to an absolute constant factor (between 4 and 8). The paper was published in Forum of Mathematics, Sigma (December 2024) without resolving the conjecture. No follow-up paper resolving or substantially advancing Conjecture 4.2 was found in a targeted search of arXiv and the authors' subsequent work.
Reviewer notes. No follow-up found. The conjecture is recent (paper published June 2024 in Forum of Mathematics, Sigma). Micha Christoph's subsequent arXiv papers (2024–2026) do not address f(n,r,s). The conjecture is closely related to the classical monochromatic connectivity problem and the results of Liu–Morris–Prince (2007). The gap between upper and lower bounds in the paper is a constant factor (4 to 8); the conjecture asserts the lower bound is the truth up to a $(\log r)^{o(1)}$ factor.
Context
The paper determines $f(n,r,s)$ — the maximum number of vertices guaranteably connected using up to $s$ colours in any $r$-edge colouring of $K_n$ — up to a logarithmic factor. The upper and lower bounds in the regime $s\leq\sqrt{r}/\log r$ differ by an absolute constant between 4 and 8 depending on divisibility properties of $r$; this conjecture posits the precise asymptotic behaviour in that regime. The authors note the gap originates in the proof technique and that under appropriate divisibility assumptions the result can be sharpened to within a factor of $2+\varepsilon$.
Source paper
The power of many colours
Noga Alon, Matija Bucić, Micha Christoph, Michael Krivelevich · 2024-06-10
https://arxiv.org/abs/2308.15387