  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^\beta \log^\gamma d)$, we
can find a $(1-\epsilon)$-$\efx$ allocation with
$O_{\epsilon}(n^{\frac{\beta}{\beta+1}}\log^{\frac{\gamma}{\beta +1}} n)$
number of discarded goods \cite{chaudhury2021improving}. The best upper bound
on $\rainbow(d)$ is improved in a series of works to $O(d^4)$
\cite{chaudhury2021improving}, $O(d^{2+o(1)})$ \cite{berendsohn2022fixed}, and
finally to $O(d^2)$ \cite{Akrami2022}.\footnote{We refer to the note at the end
of the introduction for a short discussion on the result of \cite{Akrami2022}.}
Also, via a simple observation, we have $\rainbow(d) \in \Omega(d)$
\cite{chaudhury2021improving}.
  In this paper, we introduce another problem in extremal combinatorics. For a
parameter $\ell$, we define the rainbow path degree and denote it by
$\ech(\ell)$. We show that any lower bound on $\ech(\ell)$ yields an upper
bound on $\rainbow(d)$. Next, we prove that $\ech(\ell) \in \Omega(\ell^2/\log
n)$ which yields an almost tight upper bound of $\rainbow(d) \in \Omega(d \log
d)$. This in turn proves the existence of $(1-\epsilon)$-$\efx$ allocation with
$O_{\epsilon}(\sqrt{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) \leq 2d-4$. We leverage
$\ech(\ell)$ to achieve this bound.
  Our conjecture is that the exact value of $\ech(\ell) $ is $ \lfloor
\frac{\ell^2}{2} \rfloor -1$. We provide some experiments that support this
conjecture. Assuming this conjecture is correct, we have $\rainbow(d) \in
\Theta(d)$.
