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

1 Introduction

Fair allocation of indivisible goods has been an important problem in economics and social choice theory [Aziz et al., 2015; Brams and Taylor, 1996; Steinhaus, 1948; Dubins and Spanier, 1961; Brams and Taylor, 1995; Kurokawa et al., 2018; Ghodsi et al., 2018; Lipton et al., 2004; Etkin et al., 2007; Halpern et al., 2020; Moulin, 2019; Procaccia, 2020; Pratt and Zeckhauser, 1990; Budish and Cantillon, 2012; Budish, 2011; Barman et al., 2018] with many applications in the real world. 1 In a fair allocation problem, we have a set of n agents and a set of m indivisible goods, and each agent has a valuation function that represents her utility for receiving each subset of goods. The goal is to allocate the goods to the agents fairly [Baklanov et al., 2021; Brams et al., 2017; Amanatidis et al., 2017; Barman and Krishnamurthy, 2020; Garg et al., 2019; Garg and Taki, 2020; Bouveret and Lemaˆıtre, 2016].

1 See spliddit.org and www.fairoutcomes.com for example.

A critical challenge in a fair allocation problem is to specify a reasonable notion of fairness that is simultaneously robust and practical. For the classic version of the problem that the resource is a single divisible good, a notion such as envy-freeness 2 perfectly satisfies these conditions: it is commonly accepted as a notion that represents fairness, and there are strong guarantees for the existence of envy-free divisions [Edward Su, 1999]. However, the applicability of this notion decreases significantly when dealing with indivisible goods: even for two agents and one good, envy-freeness can not be guaranteed. In recent years, several relaxations of envyfreeness have been introduced to adopt this notion to the indivisible setting. Among these notions, EFX is widely believed to be the most prominent [Caragiannis et al., 2019b; Chaudhury et al., 2021a; Chaudhury et al., 2021b; Amanatidis et al., 2020; Berger et al., 2021; Chaudhury et al., 2020; Plaut and Roughgarden, 2020].

Definition 1. An allocation is EFX (α-EFX), if for every agents i and j, agent i does not envy (α-envy) 3 agent j after removal of any good from the bundle of agent j.

See Figure 1 for examples of envy-free, EFX, and α-EFX allocations. Recent studies suggest that one can obtain strong guarantees on EFX by discarding a subset of goods [Chaudhury et al., 2021b; Caragiannis et al., 2019a]. In a pioneering work, Chaudhury, Kavitha, Mehlhorn, and Sgouritsa [2021b] show that it is possible to find an EFX allocation by discarding at most n - 1 goods. Further investigations in this direction reveal an intriguing connection between EFX and a purely combinatorial problem called Rainbow Cycle problem 4 [Chaudhury et al., 2021a]. For a multi-partite bidirected graph, a rainbow cycle is a cycle that passes each part at most once. The Rainbow Cycle problem is then defined as follows.

2 An allocation is envy-free if each agent prefers her share over the other agents' share.

3 For α < 1, agent i α-envies agent j, if the value of i for his bundle is less than α times his value for bundle of agent j.

4 The problem is also known as the Fixed Point Cycle.

Problem 1 (Rainbow Cycle). For a constant d, what is the maximum value ℓ such that there exists an ℓ-partite bidirected graph with no rainbow cycle and the following properties: (i) each part contains at least d vertices, and, (ii) each vertex receives an incoming edge from all other parts other than the one containing it. We call such a value ℓ the rainbow cycle number of d and denote it by R(d).

We refer to Section 2 for a more formal definition of this problem. The connection between the Rainbow Cycle problem and EFX notion was first observed by Chaudhury et al. [2021a]: any upper bound on R(d) yields a corresponding upper bound on the number of discarded goods.

Theorem 1 (Proved in [Chaudhury et al., 2021a]). For any constant ε ∈ (0, 1/2], if there exists constants β, γ such that R(d) ∈ O(dβ logγ d), then we can find a (1 - ε)-EFX allocation with Oϵ(n β β+1 log γ β+1 n) number of discarded goods.

The first upper bound on R(d) was also proposed by Chaudhury et al. [2021a]. They proved that R(d) ∈ O(d4 ) which bounds the number of unallocated goods by Oϵ(n 45 ). Recently, in two parallel studies [Berendsohn et al., 2022; Akrami et al., 2022], the bound on R(d) is improved to O(d2+o(1) ) and O(d2 ), yielding an upper bound of Oϵ(n 2 3 ) on the number of unallocated goods. Note that a trivial lower bound on R(d) is Ω(d). 5 Therefore, previous results leave a gap of [Ω(d),O(d2 )] between the best upper bound and the best lower bound. There is a plausible conjecture that R(d) ∈ O(d).

In this paper, we almost close this gap by showing that R(d) ∈ O(d log d). To obtain this bound, we introduce another invariant called rainbow path degree which might be of independent interest. We show that any lower bound on this invariant implies an upper bound on R(d). Next, we improve the lower bound on R(d) by providing an upper bound on the rainbow path degree.

5 See [Chaudhury et al., 2021a] for a matching example.

Before ending this section, we mention that apart from EFX and fair allocation, bounding the rainbow cycles number itself is an interesting extremal problem. Recently, Berendsohn, Boyadzhiyska, and Kozma [2022] established a connection between two combinatorial problems: Permutation Rainbow Cycle problem which is a special case of Rainbow Cycle problem, and Zero-sum Cycle problem [Alon and Krivelevich, 2021; M´esz´aros and Steiner, 2021; Alon and Caro, 1993; Alon and Dubiner, 1993; Alon and Linial, 1989; Bialostocki, 1993; Caro, 1996; Schrijver and Seymour, 1991], which is a problem in zero-sum extremal combinatorics. Here we also give an improved upper bound on the permutation rainbow cycle number. We refer to Section 3 for more details on our results and techniques.

A short note on a parallel result. We note that parallel and concurrent to this work, Akrami et al. [2022] also updated their results on arXiv. In the updated version, their upper bound on R(d) is improved from O(d2 ) to O(d log d) via a probabilistic argument. We emphasis that these two studies are parallel and independent.

2 Preliminaries

In this paper, our focus is on multi-partite bidirected graphs. For an ℓ-partite bidirected graph G, we denote its parts by V1, V2, . . . , Vℓ. Also, for a subset W ⊆ {V1, V2, . . . , Vℓ} we define G[W] to be the induced subgraph of G that only includes vertices that belong to the parts in W. Thus, G[W] has |W| parts. A path in graph G is called rainbow if it passes through each part at most once. The same definition carries over to cycles. See Figure 2 for an example.

For integers ℓ, d ≥ 0, we define Φℓ,d to be the set of all multi-partite bidirected graphs G with the following properties:

• G has exactly ℓ parts,
• each part of G has at least 1 and at most d vertices,
• each vertex of G has exactly one incoming edge from every other part,
• G admits no rainbow cycle.

In Figure 3, we show an example of a graph in Φℓ,d. We also define Φ∗,d and Φℓ,∗ as unions of Φℓ,d over all ℓ and d respectively, that is,

Also, we define R(d) as the largest ℓ such that an ℓ-partite graph exists in Φ∗,d, i.e.,

Our goal is to give an upper bound on R(d) for every d. To this aim, we introduce another property. Let G be a multipartite graph. For every vertex v ∈ G, we define fG(v) as the number of vertices in G that have a rainbow path to v except v itself. Given fG(v), for every constant ℓ, we define the rainbow path degree of ℓ, denoted by H(ℓ) as follows:

In other words, H(ℓ) is the maximum possible value that we are guaranteed that for an ℓ-partite graph G ∈ Φℓ,∗, for every vertex v ∈ G there are at least H(ℓ) different vertices with a rainbow path to v. For brevity, we call H(ℓ) the rainbow path degree of ℓ.

In order to prove an upper bound on R(d), we first prove a lower bound on H(ℓ). Interestingly, though the definition of H(ℓ) does not depend on d, our lower bound on H(ℓ) results in an almost tight upper bound on R(d).

In the last part of this section, we mention Stirling's formula for approximating factorials. For every n > 1, we have:

In the next section, we briefly review our results and techniques.

3 Our Results and Techniques

The main result of this paper is an almost tight upper bound on the rainbow cycle number by showing that R(d) ∈ ˜O(d). Our techniques are structurally different from previous methods. Indeed, a primary application of our techniques provides a simpler proof for R(d) ∈ O(d2 ). Using a more in-depth analysis, we improve this bound to O(d log d). To show this, we prove a lower bound for the rainbow path degree and show that H(ℓ) ∈ Ω(ℓ2 / log ℓ). This in turn implies that an EFX allocation exists that discards at most Oϵ(√n log n) goods.

For a better understanding of our techniques, let us overview a simple proof for R(d) ∈ O(d2 ). 6 We prove this bound by showing that H(ℓ) ∈ Ω(ℓ√ℓ). Let G ∈ Φℓ+1,∗ be an ℓ + 1 partite graph with parts {V1, V2, . . . , Vℓ+1} and let v be a vertex in Vℓ+1. By definition, we know that there are at least H(ℓ + 1) vertices that have a rainbow path to v. Denote the set of these vertices by C. Our goal is to provide a lower bound on |C|. Since the vertices in C belong to parts V1, V2, . . . , Vℓ, there is a part that contributes at most H(ℓ+1)/ℓ vertices to C. Without loss of generality, suppose that this part is Vℓ. Therefore,

In other words, at most H(ℓ + 1)/ℓ of the vertices in Vℓ have a rainbow path to v. Now, consider the vertices that have an outgoing edge to v. Since G ∈ Φℓ+1,∗, by definition, each part has a vertex with an outgoing edge to v. For each part Vi, we assume that vi is the vertex with an outgoing edge to v. Also, note that for every 1 ≤ i ≤ ℓ - 1, vertex vi has an incoming edge from part Vℓ. Since vi has an outgoing edge to v, any vertex in Vℓ that has an outgoing edge to vi has a rainbow path of length 2 to v and thus belongs to C. Since |Vℓ ∩ C| ≤ |C|/ℓ, there exists a vertex u ∈ |Vℓ ∩ C| that has outgoing edges to at least

vertices in {v1, v2, . . . , vℓ-1}. Denote these vertices by ˆ C and suppose without loss of generality that vℓ-1 ∈ ˆ C. We know that in G[V \{Vℓ-1, Vℓ+1}], the number of vertices that have a rainbow path to u is at least H(ℓ - 1). These vertices also have a rainbow path to v: consider their rainbow path to u, then go to vℓ-1 and then to v. Also, these vertices do not belong to ˆ C; otherwise, since u has outgoing edges to the vertices in ˆ C, we have a rainbow cycle. Therefore,

Using straightforward calculus one can show that Inequality (2) implies H(ℓ + 1) ∈ Ω(ℓ√ℓ).

A consequence of this lower bound is an upper bound on R(d). To see why, assume for simplicity that H(ℓ + 1) is exactly equal to ℓ√ℓ. We show Φd2+1,d is empty. To see why, consider a vertex in Vd2+1 with a non-zero outgoing degree. By definition of H(d2 + 1), the number of vertices with a rainbow path to this vertex is at least d2√d2 = d3 , which is equal to the number of vertices in {V1, V2, . . . , Vd2}. Thus, any outgoing edge from this vertex yields a rainbow cycle.

In Section 4, via a similar but more in-depth analysis, we show that H(ℓ) ∈ Ω(ℓ2 / log ℓ). A consequence of this result is the upper bound of O(d log d) on the rainbow cycle number, which leaves a gap of O(log d) factor between the upper bound and the lower bound for the rainbow cycle number. Also, in Section 6, we show that H(ℓ) ∈ O(ℓ2 ) that leaves a gap of O(log ℓ) factor between the upper bound and lower bound for the rainbow path degree.

6 We emphasize that in the interest of simplicity, our discussion in this section is not completely accurate.

In Section 6, we represent our experimental results on finding the exact value of H(ℓ). Our experiments suggest that for small values of ℓ, we have H(ℓ) = ⌊ ℓ2 2 ⌋ - 1. Assuming that this conjecture is correct for every ℓ, we have R(d) ∈ O(d). As a future direction, one can think of improving the lower bound on H(ℓ) to Ω(ℓ2 ).

Also, we consider a special case of the Rainbow Cycle problem called the Permutation Rainbow Cycle problem, where each vertex has exactly one outgoing edge to each part. As we mentioned earlier, this problem has some independent applications in extremal combinatorics. We improve the upper bound on the permutation rainbow cycle number to 2d - 3. Next, we leverage the bounds we obtain on H(ℓ) for small values of ℓ in Section 6 to improve the upper bound to 2d - 4. Furthermore, In Section 6, we consider the relation between the rainbow cycle number and the rainbow path degree in the permutation case. We show that our conjecture of H(ℓ) = ⌊ ℓ2 2 ⌋-1 implies the upper bound of 2d-3 on Rp(d) in the permutation case.

4 Upper Bound on the RainbowCycle Number

We now present our results for the Rainbow Cycle problem. This section is divided into three parts. In the first part, in Lemma 1, we show that any lower bound on rainbow path degree implies a corresponding upper bound on rainbow cycle number. Next, we prove two lower bounds on H(ℓ). As a warm up, we start by showing that H(ℓ) ∈ Ω(ℓ√ℓ). Next, we present the main result of this section, that is, H(ℓ) ∈ Ω(ℓ2 / log ℓ). This, combined with Lemma 1, yields the upper bound of R(d) ∈ O(d log d).

Lemma 1 shows a simple connection between H(ℓ) and R(d). The idea behind the proof of Lemma 1 is simple: the rainbow path degree of a vertex cannot be more than the total number of the vertices. 7

We use Lemma 1 to prove two upper bounds on R(d). First, in Lemma 2, we show that H(ℓ) ∈ Ω(ℓ√ℓ), which implies R(d) ∈ O(d2 ).

Lemma 2. For every ℓ ≥ 1, we have H(ℓ + 1) ≥ ℓ√ℓ/6.

Proof. In order to prove Lemma 2, we use induction on ℓ. For ℓ = 1, 2 we have:

7 In the interest of space, some of the proofs are deffered to the appendix.

Now, suppose that the statement holds for every ℓ′ < ℓ. Our goal is to prove the claim for ℓ. As a contradiction, suppose

This means that there exists a graph G ∈ Φℓ+1,∗ and a vertex v ∈ G, such that if we define C as the set of the vertices in G with a rainbow path to v, we have

Suppose that {V1, V2, . . . , Vℓ+1} is the set of parts in G and suppose without loss of generality that v ∈ Vℓ+1.

Claim 4.1. Fix a vertex u, and define P as the set of all rainbow paths with length at most 2 from u to v. Also, let ˆ C be the set of all different vertices that have an incoming edge from u and belong to a path in P . We have | ˆ C| ≤ 2√ℓ/3.

By Inequality (4), we know |C| < ℓ√ℓ/6. The vertices in C belong to parts V1, V2, . . . , Vℓ. Therefore, at least one of these parts contributes less than √ℓ/6 vertices to C. Suppose without loss of generality that Vℓ is one of such parts, i.e., |Vℓ ∩ C| < √ℓ/6. Since G ∈ Φℓ+1,∗, each part other than Vℓ+1 has a vertex with an outgoing edge to v. For each part Vi (i ≤ ℓ - 1), we denote this vertex by vi. Also, note that each vertex vi has an incoming edge from Vℓ. Since vi has an outgoing edge to v, any vertex in Vℓ that has an outgoing edge to vi has a rainbow path of length 2 to v and thus belongs to C. Hence, at least one of the vertices in Vℓ ∩C has outgoing edges to at least

of the vertices in {v1, v2, . . . , vℓ-1}. On the other hand, by Claim 4.1, we know that each vertex in Vℓ has at most 2√ℓ/3 outgoing edges to {v1, v2, . . . , vℓ-1}. Thus, we have

which means

that is, ℓ ≤ 16/18. But this contradicts the fact that ℓ > 2.

Corollary 1 (of Lemma 2). By choosing β = 0.5 and γ = 0 in Lemma 1, we have R(d) ∈ O(d2 ).

Now, we are ready to prove our main result. In Theorem 1, we show that H(ℓ + 1) ∈ Ω(ℓ2 / log ℓ). The structure of the proof of Theorem 1 is similar to the proof of Lemma 2. The difference is that here we generalize Claim 4.1 to consider paths with length more than 2.

Theorem 1. For every ℓ ≥ 3, we have H(ℓ+1) ≥ ℓ2 /20 ln ℓ.

Proof. We use induction on ℓ. For ℓ = 3, 4 we have:

Now, suppose that for some ℓ ≥ 5 we know that the statement of Theorem 1 holds for every 3 ≤ ℓ′ < ℓ and our goal is to prove the claim for ℓ. As a contradiction, suppose

This means that there exists a graph G ∈ Φℓ+1,∗ and a vertex v ∈ G, such that exactly H(ℓ + 1) of the vertices in G have a rainbow path to v, which is less than ℓ2 /20 lnℓ. Suppose that {V1, V2, . . . , Vℓ+1} is the set of parts in G and suppose without loss of generality that v ∈ Vℓ+1. We start by proving Claim 4.2. Claim 4.2 plays a similar role as Claim 4.1. The main difference is that in Claim 4.2, we consider paths with length more than 2.

Claim 4.2. Fix a vertex u and an integer k ≤ ℓ - 3, and define Pk as the set of all rainbow paths with length at most k from u to v. Also, let ˆ C be the set of all different vertices that have an incoming edge from u in the paths of Pk. Then, | ˆ C| ≤ ℓk/4 ln ℓ.

Now, we use Claim 4.2 to prove Claim 4.3.

Claim 4.3. Fix an integer t ≤ lnℓ. For every k ≤ t and subset W of {V1, V2, . . . , Vℓ} with ℓ - t + k parts, at least tk-1 /(k -1)! vertices of each part in W have rainbow paths with lengths at most k to v in G[W ∪ {Vℓ+1}].

By the pigeonhole principle, there exists a part Vi that contains at most H(ℓ+1)/ℓ vertices with a rainbow path to v. By choosing k = t in Claim 4.3, we have:

If we choose t = ⌊ln ℓ⌋, we have 8 :

which contradicts Inequality (6). This Completes the proof of Theorem 1.

Corollary 2 (of Theorem 1). By choosing β = 1 and γ = 1 in Lemma 1, we have R(d) ∈ O(d log d).

8 Since ⌊ln ℓ⌋ ≤ ln ℓ, the conditions of Claim 4.3 hold.

By Corollary 2, we have the upper bound of O(d log d) on R(d). Using this upper bound in Theorem 1 we obtain a new upper bound on the number of discarded goods in EFX allocations.

Corollary 3. By choosing β = 1 and γ = 1 in Theorem 1, For every constant ε ∈ (0, 1/2], we can find a (1 - ε)-EFX allocation with Oϵ(√n log n) number of discarded goods.

5 Permutation RainbowCycle

In this section, we consider the Permutation Rainbow Cycle problem. For an integer d > 0, define Πℓ,d, Π∗,d, and Πℓ,∗ respectively as subsets of Φℓ,d, Φ∗,d, and Φℓ,∗ consisting all graphs G with the additional property that each vertex in G has exactly one outgoing edge to every other part. Also, we define Rp(d) as the largest k such that a k-partite graph exists in Π∗,d, i.e.,

Our result in this section is an improved upper bound on Rp(d) for every d ≥ 3. Our method slightly improves the method of Akrami et al. [2022], wherein the authors prove the upper bound of 2d-2 on Rp(d). Throughout this section, we show that for d ≥ 4 we have Rp(d) ≤ 2d - 4. In order to prove this bound, first in Theorem 2 we show that for d ≥ 3, we have Rp(d) ≤ 2d - 3. In the proof of Theorem 2, we use the idea of constructing a sequence with certain properties. This idea has been previously used by Akrami et al. [2022] to prove the upper bound of 2d - 2. Here, we strengthen the assumptions on the sequence. Lemma 3 plays a key role in route to proving our upper bound.

We next show how we can incorporate H(ℓ) in the proof to improve the upper bound to 2d - 4. Later in Section 6, we discuss the possibility of obtaining better upper bounds on Rp(d) via a more effective incorporation of H(ℓ) in the proof. While it might be possible to obtain 2d - c upper bound for c > 4 with the same idea, we show that it is not possible to obtain an upper bound in the form of d + c for a constant c > 0 using the same method.

As a contradiction, suppose there is a graph G in Π∗,d consisting of at least 2d - 2 parts, i.e., #(G) ≥ 2d - 2. We denote by vi,j the j'th vertex in the i'th part of G.

The first important step in order to improve the previous result is stated in Lemma 3. In this lemma, we show that for every vertex v there is a vertex u with an outgoing edge to v, such that no other vertex has outgoing edge to both v and u.

Lemma 3. For each vertex v, there exists some vertex u with an outgoing edge to v such that for any vertex w with an outgoing edge to v, w does not have an outgoing edge to u.

Consider vertex v1,1. We know that in every other part, there exist a vertex with an outgoing edge to v1,1. Without loss of generality, we assume that for every j, vertex vj,1 is the vertex with an outgoing edge to v1,1.

Also, by Lemma 3, we know that there exists an index k such that vk,1 has no incoming edge from any vk′ ,1 for k′ /∈ {1, k}. Again, without loss of generality, we suppose that k = 2. Therefore, we have that for every i > 1, vertex vi,1

has an outgoing edge to v1,1 and for every i > 2, vi,1 does not have an outgoing edge to v2,1. By definition, we know that for every i ̸= 2, there exists a vertex in part Vi with an outgoing edge to v2,1. Without loss of generality, we suppose that for every i > 2, this vertex in part Vi is vi,2.

Definition 2. Consider a sequence of indices σ = σ1, σ2, ..., σk, such that σ1 = 1. Given σ, we say a vertex vσi,j is σ-reachable if there exists a rainbow path from v1,1 to vσi,j in G[{Vσ1 , Vσ2 , . . . , Vσk }]. Moreover, we say an edge in G[{Vσ1 , Vσ2 , . . . , Vσk }] is σ-rightward if it is of the form (vσj,k , vσj′,k′ ) where j < j ′ . A vertex vσi,j is σ-rightwardreachable if there exists a rainbow path from v1,1 to vσi,j via σ-rightward edges.

As we mentioned before, it is sufficient to show if G contains at least 2d-2 parts (and d ≥ 3), then we have a rainbow cycle in G. We use induction to prove this claim. For the base case d = 3, it has already shown in [Chaudhury et al., 2021a] that Rp(3) = 3, which means Rp(3) ≤ 2 × 3 - 3. Now, suppose that the claim holds for every d′ < d and our goal is to prove the claim for d. As a contradiction, we suppose that G does not admit any rainbow cycle. We start by proving Lemma 4.

Lemma 4. There exists a sequence of form σ = σ1, σ2, . . . , σ2d-3 such that for every 1 ≤ i ≤ 2d - 3, we have σi ∈ [1, 2d - 2] and the following properties hold:

• σ1 = 1.
• For every 1 ≤ i ≤ 2d - 3, we have σi ̸= 2.
• For every 2 ≤ i ≤ 2d - 4, there are ⌈ i2 ⌉ σ-rightwardreachable vertices in Vσi .
• There are d - 2 σ-rightward-reachable vertices in Vσ2d-3 .

Let σ be the sequence that satisfies the properties of Lemma 4. In Lemma 5, we prove another property for such a sequence.

Lemma 5. For every sequence σ with properties mentioned in Lemma 4 and every 2 ≤ i ≤ 2d - 3, vertices vσi,1 and vσi,2 are not σ-reachable.

Definition 3. If we consider S as a subset of {1, 2, ..., d}, part Vi is one-way S-corresponding to part Vj, if and only if for each vertex vi,k such that k ∈ S, it has an outgoing edge to vj,l ∈ Vj, such that l ∈ S.

Definition 4. Parts Vi and Vj are S-corresponding, if and only if:

• Vi is one-way S-corresponding to Vj
• Vj is one-way S-corresponding to Vi

See Figure 5 for an illustrative example.

Lemma 6. There are three pairwise {1, 2}- corresponding parts.

Finally, note that by Lemma 6, there exists three pairwise {1, 2}-corresponding parts in G. Therefore, if we consider the induced subgraph G′ of G containing vertices with indices 1, 2 in these three parts, since G ∈ Π∗,d, G′ must belong to Π∗,2. However, we know that Rp(2) = 2, which means that G′ cannot have more than two parts. This contradiction shows that, if graph contains at least 2d - 2 parts, then it has a rainbow cycle. Hence, Rp(d) ≤ 2d - 3.

Improving the upper-bound to 2d-4. We end this section by a discussion on how we can improve the upper bound to 2d - 4. Recall the definition of H(ℓ). As we show in Section 6, we have H(4) = 7. This means that for every set W of parts with |W| = 4, for any vertex v ∈ G[W], there are at least 7 other vertices that have a rainbow path to v in G[W]. Since the graph is a permutation graph, the inverse direction is also true: for any vertex v ∈ G[W], v has rainbow paths to at least 7 different vertices in G[W]. We use this fact to decrease the upper bound on Rp(d) by one.

Consider part V1 and three arbitrary parts other than V2 (i.e., V3, V4, and V5). It is guaranteed that vertex v1,1 has rainbow paths to at least 7 different vertices in these three parts. Therefore, by the pigeonhole principle, vertex v1,1 has rainbow paths to 3 vertices in one of these parts. Assume without loss of generality that this part is V5. Now, we create a shortcut in the sequence by replacing σ2, σ3, σ4, σ5 with 3, 4, 5. Note that though parts V3 and V4 might violate the properties of the sequence (e.g., rainbow paths to V5 are not necessarily σ-rightward-reachable), but V5 can be treated the same way as Vσ5 in the previous sequence, which was the first part with 3 σ-rightward-reachable vertices. Therefore, we can continue constructing the sequence from V5 in the same way as we construct the sequence (first, add σ6 and σ7, next σ8 and σ9, and so on). This way, we save one part in the sequence and therefore, the length of the sequence is reduced to 2d-4. Hence, we can conclude that if we have max(4, 2d-4) parts, then we have a rainbow cycle. As a result, Rp(d) ≤ 2d - 4 for d ≥ 4.

6 Experiments

In order to evaluate H(ℓ), we performed a set of experiments to calculate H(ℓ) for small values of ℓ. Our algorithm inputs ℓ, x and performs an exhaustive search to find a counterexample for H(ℓ) > x. By the definition of H(ℓ), this counterexample must have at most x vertices with a rainbow path to a specific vertex v. If such an example is found, we have H(ℓ) ≤ x. Otherwise, when there is no such example, we can imply that H(ℓ) > x. The overall result of running this experiment is shown in Table 1.

As you can see in Table 1, for 2 ≤ ℓ ≤ 5, the exact value of H(ℓ) is determined by the experiments. Also, for ℓ = 6, 7, our experiments provide an upper bound on H(ℓ). Recall that by Theorem 1, we have H(ℓ) ∈ Ω(ℓ2 / lnℓ). In Lemma 7, we prove an upper bound of O(n2 ) on H(ℓ).

Note that the upper bound provided by Lemma 7 exactly matches the upper bounds for H(2),H(3), and H(4). However, for H(5) this upper bound is not tight. In Figure 6, a tight example for H(5) is shown. Based on the results extracted from the experiments, our conjecture is as follows.

Note that if Conjecture 1 holds, then using Lemma 1, we have R(d) ∈ O(d).

We also performed similar experiments to evaluate Hp(ℓ) which is an analogous of H(ℓ) for permutation graphs. Formally,

where fG(v) is the number of the vertices in G that have a rainbow path to v. Interestingly, the results were exactly the same as the previous case stated.

Similar to Lemma 1, we can prove a simple relation between Hp(ℓ) and Rp(d).

Lemma 8. Given that for some ℓ, Hp(ℓ) > (d - 1)(ℓ - 1), we have Rp(d) < ℓ.

Lemma 9. For d ≥ 3, Hp(ℓ) ≥ ℓ2 2 - 1 implies Rp(d) ≤ 2d - 3.

Proof. We have

Therefore, by Lemma 8, Rp(d) < 2d - 2. Since Rp(d) is an integer, Rp(d) ≤ 2d - 3.

Lemma 9 shows that even if we prove Conjecture 2 is correct, we cannot get a better upper bound for Rp(d) with a simple connection between Rp(d) and Hp(ℓ). However, we believe proving Conjecture 2 would be a good warm-up in the way of proving Conjecture 1.