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. R (d) ) is O (d^β. log (d) ^γ), we can find a (1 − ϵ) -EFX allocation with O_ϵ (n^ (β/β+1). log (n) ^ (γ/β+1) ) number of discarded goods. The best upper bound on R (d) is improved in a series of works to O (d⁴), O (d^ (2+o (1) ) ), and finally to O (d²). Also, via a simple observation, we have R (d) ∈ Ω (d). In this paper, we introduce another problem in extremal combinatorics. For a parameter l, we define the rainbow path degree and denote it by H (l). We show that any lower bound on H (l) yields an upper bound on R (d). Next, we prove that H (l) ∈ Ω (l² / log (l) ) which yields an almost tight upper bound of R (d) ∈ Ω (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 R (d) ≤ 2d−4. We leverage H (l) to achieve this bound. Our conjecture is that the exact value of H (l) is ⌊l²/2⌋ − 1. We provide some experiments that support this conjecture. Assuming this conjecture is correct, we have R (d) ∈ θ (d).