Sharp threshold for rainbow stacking of edge-colorings

Problem 3.1 · arXiv:2405.14795

arXiv Problem high confidence— first stated 2024-05-23

Authors: Noga Alon, Colin Defant, Noah Kravitz

Status open high confidence

Problem 3.1 asks whether there is a single sharp threshold function r_0(n) governing the existence of rainbow stackings of random r-edge-colorings, sharpening the interval result of Theorem 1.1 (whose transition window has length ~(2m-1)/3). The source paper was published in the Bulletin of the London Mathematical Society in 2025 (doi: 10.1112/blms.70052), but this is the journal version of the same preprint. Search results mention a related paper by Gu extending rainbow-stacking results to hypergraphs in Discrete Mathematics 348 (2025), but this was not verified via WebFetch and may not address Problem 3.1 for graphs. No verified follow-up resolving the sharp single-threshold question was found.

Reviewer notes. The source paper was published in BLMS 2025 as doi:10.1112/blms.70052; this is the same paper, not a resolution. Problem 3.1 asks for a sharper concentration than Theorem 1.1, analogous to two-point concentration of the independence number of G(n,1/2). A paper 'A note on rainbow stackings of random edge-colorings of hypergraphs' by Gu in Discrete Mathematics 348 (2025) appeared in search results but was not verified via WebFetch and so is not cited. No confirmed resolution of Problem 3.1 was found.

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

Problem. Determine whether or not there exists a function $r_{0}\colon\mathbb{N}\to\mathbb{R}$ such that the following holds. For each $n\geq 1$, let $\chi_{1},\ldots,\chi_{m}\colon\binom{[n]}{2}\to\mathcal{C}_{r}$ be independent uniformly random $r$-edge-colorings. If $r=r(n)$ satisfies $r(n)<r_{0}(n)$, then with high probability, there does not exist a rainbow stacking of $\chi_{1},\ldots,\chi_{m}$. If $r=r(n)$ satisfies $r(n)>r_{0}(n)$, then with high probability, there exists a rainbow stacking of $\chi_{1},\ldots,\chi_{m}$.

Context

Theorem 1.1 shows that the existence of rainbow stackings exhibits a sharp threshold, with the transition occurring within an interval of length roughly $(2m-1)/3$. The authors pose whether the transition is even sharper — i.e., whether a single threshold function $r_0$ governs the transition exactly. The critical value of $r$ is on the order of $n/\log n$, making such a sharp transition more dramatic than, for example, the 2-point concentration of the independence number of $G(n,1/2)$.

Source paper

Rainbow Stackings of Random Edge-Colorings
Noga Alon, Colin Defant, Noah Kravitz · 2024-05-23
https://arxiv.org/abs/2405.14795