Transition threshold between f and g
Question 4.3 · arXiv:2308.15387
Status open high confidence
Question 4.3 of arXiv:2308.15387 asks for the precise threshold in s (as a function of r) at which the functions f(n,r,s) and g(n,r,s) — measuring, respectively, the maximum guaranteed connected-component size and the minimum guaranteed vertex-coverage when using up to s colors in an r-edge-coloring of K_n — transition from behaving differently to behaving similarly. The paper establishes that they differ for s ≪ √r/log r and agree for s ≥ √(r log r), leaving the exact crossover point open. No follow-up work resolving this question was found in the indexed literature.
Reviewer notes. The verbatim statement of Question 4.3 was not recoverable from the HTML/PDF renders attempted (Section 4 was truncated in all fetched versions). The context is clear: it asks for the exact threshold s*(r) separating the regime where f and g have different asymptotic behaviour from the regime where they coincide. The paper is published in Forum of Mathematics, Sigma (Cambridge Core, December 2024). No citing paper addressing Question 4.3 was found across three web searches and three fetches.
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.
Also stated in
- The power of many colours (2024-06-10)
- The power of many colours (2024-06-10)
- The power of many colours (2024-06-10)
Notes. Statement not provided in input excerpt; existence inferred from the theorem-environment list and the surrounding context of Conjecture 4.2.
Source paper
The power of many colours
Noga Alon, Matija Bucić, Micha Christoph, Michael Krivelevich · 2024-06-10
https://arxiv.org/abs/2308.15387