The sharp threshold for rainbow stackings of random edge-colourings

Guorui Ma; Hong Liu; Yangrui Xiang; Zhifei Yan

arxiv: 2606.31376 · v1 · pith:USDFNFEXnew · submitted 2026-06-30 · 🧮 math.CO

The sharp threshold for rainbow stackings of random edge-colourings

Hong Liu , Guorui Ma , Yangrui Xiang , Zhifei Yan This is my paper

Pith reviewed 2026-07-01 05:03 UTC · model grok-4.3

classification 🧮 math.CO

keywords rainbow stackingrandom edge-coloringssharp thresholdconflict graphchromatic polynomialweighted permutation sumcomplete graphphase transition

0 comments

The pith

The threshold for rainbow stackings of m random r-edge-colorings of K_n includes an additive constant term of (2m-1)/6 beyond the main term m binom(n,2)/(2 log(n!)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper pins down the exact constant in the phase transition for the existence of rainbow stackings of m independent uniform random r-edge-colorings of the complete graph on n vertices. It proves that the critical value of r sits at m times the number of edges divided by twice the log of n factorial plus the fixed offset (2m-1)/6, with the transition window shrinking to width o(1) after scaling by 1/(log n)^2. A reader would care because the result upgrades an earlier constant-order window to a sharp threshold that equals the ceiling of the displayed expression for a density-one set of n, resolving the precise location of the transition. The argument proceeds by expanding the chromatic polynomial of an auxiliary conflict graph and refining the estimate of a weighted sum over permutations.

Core claim

For every fixed m≥2 and every ω(n)→∞, with high probability there is no rainbow stacking if r≤ m binom(n,2)/(2 log(n!))+(2m-1)/6 - ω(n)/(log n)^2, while with high probability there is one if r≥ m binom(n,2)/(2 log(n!))+(2m-1)/6 + ω(n)/(log n)^2. This yields the exact threshold ceil(m binom(n,2)/(2 log(n!))+(2m-1)/6) for a density-one set of integers n.

What carries the argument

Chromatic-polynomial expansion for an auxiliary conflict graph combined with a refined estimate of the associated weighted permutation sum

If this is right

The transition window narrows to width o(1) after the additive constant is included.
The ceiling of the displayed expression serves as the exact threshold for rainbow stackings on a density-one set of n.
Existence holds with high probability above the ceiling and fails with high probability below it.
Earlier constant-order window bounds are sharpened to locate the constant term precisely.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same expansion technique might locate additive constants in thresholds for related objects such as rainbow decompositions or Latin rectangles.
Numerical verification on small n could test whether the predicted ceiling matches observed transition points.
The method may adapt to colorings with non-uniform distributions or to graphs other than the complete graph.
Links via the chromatic polynomial invite connections to enumeration problems in extremal graph theory.

Load-bearing premise

The chromatic-polynomial expansion for the auxiliary conflict graph combined with the refined estimate of the weighted permutation sum must hold with sufficient precision to isolate the constant term (2m-1)/6 without additional error terms that would shift the threshold location.

What would settle it

A direct enumeration or Monte-Carlo check on a sequence of moderate n values showing that the probability of a rainbow stacking jumps from near zero to near one at an integer different from the predicted ceiling would falsify the exact-threshold claim.

read the original abstract

A rainbow stacking of $m$ independent, uniformly random $r$-edge-colourings of $K_n$ is a tuple of vertex permutations that superimposes the colourings such that no two edges of the same colour overlap. The study of the critical palette size $r$ required for the existence of such stackings was recently initiated by Alon, Defant, and Kravitz [Bull. Lond. Math. Soc., 57, 2025], who bounded the phase transition within a constant-order window around $\frac{m\binom{n}{2}}{2\log(n!)}$. We determine the constant term in this transition. For every fixed $m\ge2$ and every function $\omega(n)\to\infty$, with high probability there is no rainbow stacking if $$r\le \frac{m\binom{n}{2}}{2\log(n!)}+\frac{2m-1}{6}-\frac{\omega(n)}{(\log n)^2},$$ while with high probability there is one if $$r\ge \frac{m\binom{n}{2}}{2\log(n!)}+\frac{2m-1}{6}+\frac{\omega(n)}{(\log n)^2}.$$ Our proof combines a chromatic-polynomial expansion for an auxiliary conflict graph with a refined estimate of the associated weighted permutation sum. Our result yields the exact threshold $\Big\lceil \frac{m\binom{n}{2}}{2\log(n!)}+\frac{2m-1}{6}\Big\rceil$ for a density-one set of integers $n$, resolving a problem of Alon, Defant and Kravitz.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Pins down the exact additive constant (2m-1)/6 in the rainbow stacking threshold, sharpening the prior constant window.

read the letter

This paper closes the remaining gap from Alon-Defant-Kravitz by locating the precise constant term in the phase transition for rainbow m-stackings of random r-edge-colorings of K_n. The threshold sits at m binom(n,2)/(2 log(n!)) + (2m-1)/6, with the usual omega(n) windows on either side, and the ceiling expression holds for a density-one set of n.

The main advance is the combination of a chromatic-polynomial expansion on the auxiliary conflict graph with a tighter estimate on the weighted permutation sum. That lets them extract the constant without error terms large enough to move the location. The argument stays inside the random-coloring model and does not rely on fitted parameters or prior self-citations, so the derivation looks direct.

The soft spot is the usual one for these sharp-threshold arguments: the expansion and sum estimates must be accurate enough to isolate exactly (2m-1)/6 rather than (2m-1)/6 plus a hidden o(1) that could shift the ceiling for some n. The abstract names the tools and claims the precision, but the full verification sits in the details of those estimates. Nothing in the setup suggests a structural flaw that would invalidate the result.

The work is aimed at people already working on probabilistic thresholds for permutations and colorings. A reader interested in similar phase-transition techniques would pick up the method even if the exact constant is not their main concern. It is a clean resolution of the open problem left by the 2025 paper and deserves a serious referee.

Referee Report

0 major / 0 minor

Summary. The paper determines the sharp threshold for rainbow stackings of m fixed independent uniform random r-edge-colorings of K_n. It proves that for ω(n)→∞ the probability of existence transitions from o(1) to 1-o(1) across the window of width 2ω(n)/(log n)^2 centered at m binom(n,2)/(2 log(n!)) + (2m-1)/6, yielding the exact ceiling threshold for a density-one set of n and resolving a problem of Alon-Defant-Kravitz.

Significance. The result isolates the precise additive constant (2m-1)/6 via a parameter-free argument that combines chromatic-polynomial expansion of an auxiliary conflict graph with a refined weighted-permutation-sum estimate. It upgrades the earlier constant-order window to an exact threshold statement that is falsifiable for most n and directly addresses the open question posed in the prior work.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of the manuscript. We are pleased that the referee finds the result significant and recommends acceptance.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives the sharp threshold for rainbow stackings via an auxiliary conflict graph whose chromatic polynomial is expanded, combined with a refined estimate of the weighted permutation sum. This proceeds directly from the random r-edge-coloring model of K_n without any fitted parameters renamed as predictions, self-definitional loops, or load-bearing self-citations. The cited prior work (Alon-Defant-Kravitz) is by different authors and supplies only the coarse window that is refined here; the constant (2m-1)/6 is isolated by explicit expansion rather than by ansatz or renaming. The argument is parameter-free and externally falsifiable for density-one n, satisfying the criteria for a non-circular derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard asymptotic combinatorics and the validity of two analytic estimates; no free parameters or new entities are introduced.

axioms (2)

standard math Standard probabilistic method and asymptotic enumeration for random graphs and permutations as n→∞ with m fixed
Underpins all whp statements and the main-term expression involving log(n!).
domain assumption The chromatic-polynomial expansion and refined weighted-permutation-sum estimates isolate the constant (2m-1)/6 without residual terms that alter the threshold
Directly invoked to obtain the sharp location of the phase transition.

pith-pipeline@v0.9.1-grok · 5831 in / 1472 out tokens · 76702 ms · 2026-07-01T05:03:29.238140+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references

[1]

N. Alon, C. Defant, and N. Kravitz. Rainbow stackings of random edge-colorings.Bull. Lond. Math. Soc., 57(6):1656–1670, 2025

2025
[2]

C. Borgs. Absence of zeros for the chromatic polynomial on bounded degree graphs.Combin. Probab. Comput., 15(1-2):63–74, 2006

2006
[3]

Fadnavis

S. Fadnavis. A note on the shameful conjecture.European J. Combin., 47:115–122, 2015

2015
[4]

A. D. Sokal. Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput., 10(1):41–77, 2001. ECOPRO, Institute for Basic Science, 55 Expo-ro, Yuseong-gu, Daejeon, 34126, Korea Email address:{hongliu,zhifeiyan}@ibs.re.kr Shanghai Institute for Mathematics and Interdisciplinary Sciences (SIMIS), Shan...

2001

[1] [1]

N. Alon, C. Defant, and N. Kravitz. Rainbow stackings of random edge-colorings.Bull. Lond. Math. Soc., 57(6):1656–1670, 2025

2025

[2] [2]

C. Borgs. Absence of zeros for the chromatic polynomial on bounded degree graphs.Combin. Probab. Comput., 15(1-2):63–74, 2006

2006

[3] [3]

Fadnavis

S. Fadnavis. A note on the shameful conjecture.European J. Combin., 47:115–122, 2015

2015

[4] [4]

A. D. Sokal. Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput., 10(1):41–77, 2001. ECOPRO, Institute for Basic Science, 55 Expo-ro, Yuseong-gu, Daejeon, 34126, Korea Email address:{hongliu,zhifeiyan}@ibs.re.kr Shanghai Institute for Mathematics and Interdisciplinary Sciences (SIMIS), Shan...

2001