Aharoni’s rainbow cycle conjecture holds up to an additive constant

Let $D$ be a simple $n$-vertex digraph with minimum out-degree at least $r$. We create an edge-coloured graph $G$ from $D$ with $V(G)=V(D)$ as follows. For each arc $(u,v)\in A(D)$ we create an edge $uv\in E(G)$ with color $u$. Note that $G$ has $n$ color classes of size at least $r$ (since $D$ has minimum out-degree at least $r$). Moreover, since $D$ is a simple digraph it follows that $G$ is a simple edge-colored graph. By Conjecture 1.3, $G$ contains a rainbow cycle of length at most $\lceil n/r\rceil$. This rainbow cycle necessarily corresponds to a directed cycle in $D$. ∎

Since we have already noted that Conjecture 1.3 holds when $r=1$, we may assume $r\geqslant 2$. Next, let $G$’ be obtained from $G$ by deleting edges so that each color class has size exactly $r$. By applying Theorem 1.7 to $G^{\prime}$ and noting that $\mathsf{def}_{r}(G^{\prime})=0$, it follows that $G^{\prime}$ (and hence also $G$) contains a rainbow cycle of length at most $\frac{n}{r}+\alpha_{r}$. ∎

The statement is obviously true if $g\leqslant 2r-2$. Thus, we may assume that $g\geqslant 2r-1$. It follows by Theorem 2.3 that

as desired. ∎

See Figure 1 for an example with $m=7$. For each $u\in R$, we define a function $p:R\to R$ as follows. If $u\in X$, then $p(u)=u$. If $u\notin X$, but some $M$-neighbor $v$ of $u$ is in $X$, we arbitrarily choose one such $v$, and define $p(u)=v$. Otherwise, define $p(u)=u_{i}$, where $i$ is the minimum index such that $u_{i}$ is an $M$-neighbor of $u$. For example, in Figure 1, we have $p(u_{4})=u_{2}$.

Let $u,v\in R$. Let $P^{u}$ be the path beginning at $u$ and repeatedly applying the map $p$ until we reach a vertex in $X$. Define $P^{v}$ analogously, but starting from $v$.

First suppose there exists $u_{a}\in V(P^{u})$ and $u_{b}\in V(P^{v})$ such that $u_{a}$ and $u_{b}$ have a common $M$-neighbor in $\{u_{1},\dots,u_{m}\}$. Choose $u_{a}$ and $u_{b}$ such that $a+b$ is maximum. By symmetry, we may assume $a>b$. Let $P_{a}$ be the subpath of $P^{u}$ from $u$ to $u_{a}$, and let $P_{b}$ be the subpath of $P^{v}$ from $v$ to $u_{b}$. Let $Q_{a}=P_{a}\setminus\{u_{a}\}$ and $Q_{b}=P_{b}\setminus\{u_{b}\}$. By the maximality of $a+b$,

Rearranging, we have

Let $u_{\ell}$ be a common $M$-neighbor of $u_{a}$ and $u_{b}$ in $\{u_{1},\dots,u_{m}\}$. Then $P_{a}\cup P_{b}\cup\{u_{a}u_{\ell},u_{b}u_{\ell}\}$ is a rainbow path consisting of colors in $C_{X}\cup C(M)$ from $u$ to $v$ in $G[R]$ of length at most

as required.

For the remaining case, let $u^{\prime}\in X$ and $v^{\prime}\in X$ be the other ends of $P^{u}$ and $P^{v}$. Let $Q^{u}=P^{u}\setminus u^{\prime}$ and $Q^{v}=P^{v}\setminus v^{\prime}$, and let $S^{u}$ be $Q^{u}$ minus its last vertex and $S^{v}$ be $Q^{v}$ minus its last vertex. If both $u$ and $v$ are in $X$, then we are done by (3). Thus, by symmetry, we may assume that $u=u_{a}$ for some $a\in[m]$ and that either $v\in X$ or $v=u_{b}$ for some $b<a$. By the previous case, we may assume that for all $x\in V(Q^{u})$ and $y\in V(Q^{v})$, $x$ and $y$ do not have any common $M$-neighbors in $\{u_{1},\dots,u_{m}\}$. Therefore,

Rearranging, we have

By (3), there is a rainbow path $P$ consisting of colors in $C_{X}$ from $u^{\prime}$ to $v^{\prime}$ in $G[X]$ of length at most $d$. Since $C_{X}\cap C(M)=\emptyset$, $P^{u}\cup P^{v}\cup P$ is a rainbow path consisting of colors in $C_{X}\cup C(M)$ from $u$ to $v$ in $G[R]$ of length at most

as required. This completes the proof of the lemma. ∎

First suppose $A$ is a star class. Then $A$ is covered by at most

sets $N^{\prime}\subseteq N$ of size $k$ (since $|A|\geqslant 2$).

So, suppose instead that $A$ is a non-star class. If there exists a matching $M=\{u_{1}v_{1},u_{2}v_{2}\}$ of size $2$ in $A$, then we note that every set of vertices which covers $A$ must contain either $u_{1}$ or $v_{1}$, and either $u_{2}$ or $v_{2}$. It follows that $A$ is covered by at most

subsets of size $k$ in $N$, as required.

Finally, suppose that there does not exist a matching of size 2 in $A$. Since $A$ is not a star, it follows that $A$ is a triangle. Then the number of subsets of $N$ of size $k$ that cover $A$ is at most

This completes the proof. ∎

First suppose that fewer than $\frac{(|N|-k)^{2}}{4k^{2}}$ color classes contain an edge with an end in $N$. By Claim 4.1, at most

subsets of $N$ of size $k$ cover some color class. Therefore, there exists a subset $N^{\prime}\subseteq N$ of size $k$ such that $N^{\prime}$ does not cover any color class. By choosing an edge of each color with neither end in $N^{\prime}$ we obtain a rainbow subgraph $H$ of $G$ with $|E(H)|=n$ and $|V(H)|\leqslant|V(G)\setminus N^{\prime}|=n-k$. In particular, $H$ is excess-$k$. Since $r\geq 2$ and $n\geq k$ (otherwise we have a rainbow cycle of length at most $k<\alpha_{r}$),  Corollary 2.2 gives that $H$ has a rainbow cycle of length at most

as desired.

So, we may assume that at least $\frac{(|N|-k)^{2}}{4k^{2}}$ color classes have at least one edge with an end in $N$. Note that $|N|-k\geq|N|/2$ since $|N|>f(r)\geq 2k$. Therefore, by averaging, there exists a vertex $v\in N$ with at least $\frac{|N|}{16k^{2}}>\frac{f(r)}{16k^{2}}=5r^{2}$ colors having at least one edge incident with $v$. Therefore, there exists a rainbow star $T$ centred at $v$ with $|V(T)|>5r^{2}.$

Now, let $X$ be a maximal set of vertices containing $V(T)$ such that

1. (1)

   exactly $|X|-1$ colors of $G$ appear in $G[X]$,

2. (2)

   for all $u,v\in X$, there exists a rainbow path from $u$ to $v$ in $G[X]$ with length at most

   $$\frac{|X|+\sum_{c\in C(X)}(r-|c_{G}|)}{r}-5r+2,$$

where $|c_{G}|$ is the size of the color class in $G$, and $C(X)$ is the set of colors which appear in $G[X]$.

Note that $V(T)$ satisfies the first condition since otherwise $G[V(T)]$ contains a rainbow triangle and we have obtained a short rainbow cycle. Moreover, $V(T)$ satisfies the second condition since $|V(T)|>5r^{2}$ and every color class has size at most $r$. Since $V(T)$ satisfies both conditions and clearly $V(T)\subseteq V(T)$, it follows that $V(T)$ is a valid candidate and therefore $X$ is a well-defined set.

Now, let $u_{1},\cdots,u_{m}$ be a maximal sequence of vertices in $G\setminus X$ such that there is a star color class $A_{i}$ centred at $u_{i}$ with $V(A_{i})\setminus\{u_{i}\}\subseteq X\cup\{u_{1},\dots,u_{i-1}\}$. Note that $u_{1},\dots,u_{m}$ exist, since we allow $m=0$. Let $T^{\prime}=X\cup\{u_{1},\cdots,u_{m}\}$, $c_{i}$ denote the color of $A_{i}$, and $C^{\prime}(T^{\prime})=C(X)\cup\{c_{1},\cdots,c_{m}\}$. Let $d:=\frac{|X|+\sum_{c\in C(X)}(r-|c_{G}|)}{r}-5r+2$. By Lemma 3.1, for all $u,v\in T^{\prime}$ there exists a rainbow path in $G[T^{\prime}]$ from $u$ to $v$ consisting of colors in $C(X)\cup\{c_{1},\dots,c_{m}\}$ of length at most

It follows that exactly $|X|-1+m=|T^{\prime}|-1$ colors appear in $G[T^{\prime}]$; otherwise, $G[T^{\prime}]$ contains a rainbow cycle of length at most

Therefore, $C^{\prime}(T^{\prime})=C(T^{\prime})$. Now, let $\mathcal{A}$ be the set of color classes $A$ such that no edge of $A$ is in $G[T^{\prime}]$ and some edge in $A$ has exactly one end in $T^{\prime}$. For each $A\in\mathcal{A}$, choose an edge $e_{A}\in A$ with exactly one end in $T^{\prime}$, and let $Y\subseteq V(G)\setminus T^{\prime}$ be the set of ends of these edges not in $T^{\prime}$. Note that $|Y|=|\mathcal{A}|$; otherwise $G[T^{\prime}\cup Y]$ contains a rainbow cycle of length at most

Moreover, exactly $|T^{\prime}\cup Y|-1$ colors appear in $G[T^{\prime}\cup Y]$; otherwise $G[T^{\prime}\cup Y]$ contains a rainbow cycle of length at most

Note that when adding $Y$ to $T^{\prime}$ the ‘rainbow diameter’ increases by at most $2$, regardless of the size of $Y$. Therefore, for all $u,v\in T^{\prime}\cup Y$, there exists a rainbow path from $u$ to $v$ in $G[T^{\prime}\cup Y]$ of length at most

It follows that $|Y|\leqslant 4r-1$; otherwise $T^{\prime}\cup Y$ contradicts the maximality of $X$. Now, we contract $T^{\prime}$ to a single vertex, delete all edges with colors in $T^{\prime}$, and remove parallel edges of the same color. Let the resulting edge-colored graph be $G^{\prime}$. Note that by the construction of $T^{\prime}$, $G^{\prime}$ contains $|V(G^{\prime})|$ color classes of size at least $2$, and at most $4r-1$ color classes have less edges in $G^{\prime}$ than they do in $G$ (since $|\mathcal{A}|\leqslant 4r-1$). By induction on $n$, $G^{\prime}$ has a rainbow cycle $D$ of length at most

Observe that $D$ is either a rainbow cycle in $G$, or a rainbow path between $u$ and $v$, for some $u,v\in T^{\prime}$. If the former holds, then

since $|V(G^{\prime})|+(4r-1)(r-2)\leqslant|V(G^{\prime})|+5r^{2}-1\leqslant|V(G^{\prime})|+|T^{\prime}|-1=n$.

In the latter case, from our earlier application of Lemma 3.1, we have that there exists a rainbow path $P$ in $G[T^{\prime}]$ from $u$ to $v$ of length at most

By the construction of $G^{\prime}$, the colors used in $P$ are disjoint from the colors used in $D$. Therefore, $D\cup P$ is a rainbow cycle in $G$ of length at most

since $1+(4r-1)(r-2)\leqslant r(5r-4)$ simplifies to $r^{2}+5r\geqslant 3$ which is true for $r\geq 2$. This completes the proof of the lemma. ∎

Let $N=\{v_{1},v_{2},\cdots,v_{t}\}$ be an arbitrary fixed ordering of the vertices of $N$. Let $U=V(G)\setminus N$ and choose a galaxy $M:=(M_{u}:u\in U)$ rooted at $U$ by arbitrarily choosing a star class $M_{u}$ of color $c_{u}$ centred at $u$ for each $u\in U$. An edge $e\in E(G)$ is an $M$-edge if $e\in E(M_{u})$ for some $u\in U$. For $Y\subseteq V(G)$ we define $\gamma(Y)$ to be the set of star vertices $u\in V(G)\setminus Y$ such that at least one $M$-neighbor of $u$ is in $Y$.

For each $X\subseteq V(G)$, let $C_{M}(X)$ be the set of $M$-colors which have an edge with both ends in $X$. Now, we iteratively construct pairwise-disjoint sets of vertices $T_{1},T_{2},\cdots,T_{t}$ of $G$ and associated constants $d_{1},d_{2},\cdots,d_{t}$ such that for all $j\in[t]$, we have the following four properties:

1. (1)

   $T_{j}\cap N=\{v_{j}\}$.
   

2. (2)

   For each star vertex $v\notin\bigcup_{i=1}^{j}T_{j}$, $v$ has at least one $M$-neighbor which is not in $\bigcup_{i=1}^{j}T_{j}$.
   

3. (3)

   For each pair of vertices $u,v\in T_{j}$, there exists a rainbow path of $M$-edges between $u$ and $v$ in $G[T_{j}]$ of length at most

   $$\frac{|T_{j}|+\sum_{c\in C_{M}(T_{j})}(r-|c_{G}|)}{r}+d_{j}.$$

   
   
4. (4)

   $\sum_{i=1}^{j}d_{i}+|\gamma(\bigcup_{i=1}^{j}T_{i})|\leqslant(4r+1)j$.
   

Fix $j\in[t]$, and suppose we have already constructed $T_{1},\cdots,T_{j-1}$ with the associated constants $d_{1},\cdots,d_{j-1}$ such that they satisfy the above four properties. Let $G_{j}:=G\setminus\bigcup_{i=1}^{j-1}T_{i}$. For $X\subseteq V(G_{j})$, let $s(X)$ be the set of star vertices $x\in X$ such that at least one $M$-neighbor of $x$ is in $\bigcup_{i=1}^{j-1}T_{i}$. Let $X$ be a maximal set of vertices of $G_{j}$ such that $X\cap N=\{v_{j}\}$, and for each pair of vertices $u,v\in X$, there exists a rainbow path of $M$-edges between $u$ and $v$ in $G[X]$ of length at most