Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap

Recently, some studies on the fair allocation of indivisible goods notice a connection between a purely combinatorial problem called the Rainbow Cycle problem and a fairness notion known as efx: assuming that the rainbow cycle number for parameter d (i.e. rainbow(d)) is O(dβ logγ d), we can find a (1-ε)-efx allocation with Oε(n^fracββ+1log^fracγβ +1 n) number of discarded goods citechaudhury2021improving. The best upper bound on rainbow(d) is improved in a series of works to O(d4) citechaudhury2021improving, O(d2+o(1)) citeberendsohn2022fixed, and finally to O(d2) citeAkrami2022.footnoteWe refer to the note at the end of the introduction for a short discussion on the result of citeAkrami2022. Also, via a simple observation, we have rainbow(d) ∈ Omega(d) citechaudhury2021improving. In this paper, we introduce another problem in extremal combinatorics. For a parameter ℓ, we define the rainbow path degree and denote it by ech(ℓ). We show that any lower bound on ech(ℓ) yields an upper bound on rainbow(d). Next, we prove that ech(ℓ) ∈ Omega(ℓ2/log n) which yields an almost tight upper bound of rainbow(d) ∈ Omega(d log d). This in turn proves the existence of (1-ε)-efx allocation with Oε(√n log n) number of discarded goods. In addition, for the special case of the Rainbow Cycle problem that the edges in each part form a permutation, we improve the upper bound to rainbow(d) ≤ 2d-4. We leverage ech(ℓ) to achieve this bound. Our conjecture is that the exact value of ech(ℓ) is lfloor fracℓ22 rfloor -1. We provide some experiments that support this conjecture. Assuming this conjecture is correct, we have rainbow(d) ∈ Theta(d).