Pith's one-line read
The rainbow cycle number is linear: every multipartite digraph with the in-neighbor property and no rainbow cycle has fewer than e·d parts of size at most d, which yields partial (1−ε)-EFX with only O(√(n/ε)) unallocated goods.
desk verdict
Clean elementary proof that R(d)<ed, resolving the linear conjecture and giving the best asymptotic unallocated-goods bound the rainbow-cycle reduction can deliver.
read the letter →
A machine-rendered reading of the paper's core claim, the
machinery that carries it, and where it could break.
The reading
Whether every additive fair-division instance has a complete EFX allocation is still open. A standard workaround leaves some goods unallocated and asks only for (1−ε)-EFX. Bounds on a combinatorial quantity called the rainbow cycle number R(d) convert directly into bounds on how many goods must be left out. This paper proves the long-conjectured linear upper bound R(d) < e d, improving the previous O(d log d). The resulting guarantee is a partial (1−ε)-EFX allocation with O(√(n/ε)) unallocated goods—the best asymptotic number the rainbow-cycle reduction can ever deliver—and a randomized algorithm finds it in expected polynomial time.
What carries the argument
The packing inequality: after choosing one in-neighbor from each other class for every vertex, each pair (permutation of the classes, terminal vertex) builds a unique rainbow path; distinct pairs produce distinct transversals, because two different orders on the same vertex set would create a rainbow cycle. Counting these paths yields the factorial-versus-product inequality.
What would settle it
Exhibit a directed multipartite digraph with the in-neighbor property, part size at most d, no rainbow cycle, and at least ⌈e d⌉ parts; or, for a concrete small d, decide by exhaustive or SAT search whether R(d) already meets or exceeds ⌊e d⌋.
In any directed k-partite graph whose every vertex has an in-neighbor in every other part and that contains no rainbow cycle, the packing inequality (k−1)! ∑|V_i| ≤ ∏|V_i| holds. When every part has size at most d this forces k! ≤ d^{k−1}, hence k < e d, so the rainbow cycle number satisfies R(d) < e d.
Load-bearing premise
The translation from the combinatorial bound into an EFX guarantee rests entirely on an earlier reduction that splits leftover goods into high-demand items (at most 2n/(ε d) of them) and low-demand items whose “champion graph” is rainbow-cycle-free and therefore of size at most R(d).
Editorial extensions
If this is right
Every additive n-agent instance admits a partial (1−ε)-EFX allocation with O(√(n/ε)) unallocated goods, found by a randomized expected polynomial-time algorithm.
When agents use only q distinct valuations the same argument leaves only O(√(q/ε)) goods unallocated.
Starting from a suitable high-Nash-welfare seed yields the same unallocated-goods bound while preserving a (1/(2−ε))-approximation to maximum Nash welfare.
The same counting shows the rainbow path degree H(ℓ) is Θ(ℓ²).
The bound supplies a short alternate proof that every finite group Γ has zero-sum cycle number n(Γ) = O(|Γ|).
Reading between the lines
Editorial extensions of the paper, not claims the author makes directly.
Because R(d) ≥ d is already known, the expression 2n/(ε d) + R(d) is minimized at Θ(√(n/ε)); further improvements inside the rainbow-cycle framework cannot beat this square-root barrier.
The still-open conjecture R(d) = d would simultaneously give the sharp zero-sum bound n(Γ) ≤ |Γ| + 1 for every finite group and the cleanest possible constant in the EFX reduction.
Derandomizing the O(k²)-time rainbow-cycle finder at the linear threshold remains open and would turn the whole EFX procedure deterministic.