In this post I would like to discuss a beautiful generalization of the Caccetta-Häggkvist conjecture, due to Ron Aharoni [1]. This post is based on joint work with Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Bojan Mohar, and Amanda Montejano [3]. Recall that the Caccetta-Häggkvist conjecture is the following conjecture about directed cycles in digraphs.

**Conjecture 1 **(Caccetta and Häggkvist [2]). For all positive integers $n,r$, every simple $n$-vertex digraph with minimum outdegree at least $r$ contains a directed cycle of length at most $\lceil \frac{n}{r} \rceil$.

Here, a digraph is *simple* if for all pairs of vertices $u, v$, there is at most one arc from $u$ to $v$. Despite considerable effort (especially for the case $r=\frac{n}{3}$), the Caccetta-Häggkvist conjecture remains open. See Sullivan [4] for a survey of results.

Faced with a seemingly impenetrable problem, the most natural thing to do of course is to try and solve an even harder problem. The following conjecture of Aharoni [1] is about rainbow cycles in edge-coloured graphs.

**Conjecture** **2**** **(Aharoni [1]). Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $r$. Then $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{r} \rceil$.

Here, *rainbow* means that no two edges of the cycle are the same colour. Note that Conjecture 2 is false if we allow graphs with parallel edges, since we could take $G$ to be a Hamiltonian cycle with ‘doubled’ edges and colour $E(G)$ so that $e$ and $f$ have the same colour if and only if they are parallel edges.

We now show that the following weakening of Aharoni’s conjecture still implies the Caccetta-Häggkvist conjecture.

**Conjecture 3**. Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $r$. Then $G$ contains a properly edge-coloured cycle $C$ of length at most $\lceil \frac{n}{r} \rceil$.

*Proof of the implication. *Let $D$ be a simple digraph with vertex set $\{1, \dots, n\}$ and minimum outdegree at least $r$. Let $G$ be the graph obtained from $D$ by forgetting the orientations of arcs. Moreover, colour each edge $ij$ of $G$ with colour $i$ if $(i,j)$ is an arc of $D$. Clearly, this colouring uses $n$ colours. Since $D$ has minimum outdegree at least $r$, each colour class has size at least $r$. By Conjecture 3, $G$ contains a properly edge-coloured cycle $C$ of length at most $\lceil \frac{n}{r} \rceil$. Since $C$ is properly edge-coloured, $C$ must correspond to a directed cycle in $D$.

Unlike the Caccetta-Häggkvist conjecture, Aharoni’s conjecture has a very natural matroid generalization. Since this is a matroid blog, this is a good thing. All notions in Aharoni’s conjecture easily carry over to matroids, except possibly the number of vertices $n$ of $G$. Since $n-1$ is the number of edges of a spanning tree of $G$, the most natural thing to say is that the rank of the matroid is $n-1$.

**Conjecture 4.** Let $M$ be a simple rank-$(n-1)$ matroid and $c$ be a colouring of $E(M)$ with $n$ colours, where each colour class has size at least $r$. Then $M$ contains a rainbow circuit of size at most $\lceil \frac{n}{r} \rceil$.

Unfortunately, if you keep on making a hard problem harder, at some point it becomes false, and we have reached that point. To see this, note that the the uniform matroid $U_{n-1, m}$ does not contain *any* circuits of size less than $n$.

What can we hope to prove about Aharoni’s conjecture, then? Well, even the Caccetta-Häggkvist conjecture is only known to hold for a few values of $r$. For example, the case $r=2$ was proved by Caccetta and Häggkvist themselves [2]. The case $r=3$ was proved by Hamidoune [5], and $r \in \{4,5\}$ by Hoàng and Reed [6]. Our main result is that Aharoni’s conjecture holds for $r=2$.

**Theorem 1. **Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. Then $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{2} \rceil$.

The proof is not too difficult (it uses the block-cut tree and ear-decompositions), although we also use the $r=2$ case of the Caccetta-Häggkvist conjecture as a black box. It is a nice open problem if our main theorem can be proved directly, without using the corresponding result for directed graphs.

Equivalently, Theorem 1 shows that Conjecture 4 holds for graphic matroids when $r=2$. We now show that this is also true for cographic matroids.

**Theorem 2.** Let $M$ be a simple rank-$(n-1)$ cographic matroid and $c$ be a colouring of $E(M)$ with $n$ colours, where each colour class has size at least $2$. Then $M$ contains a rainbow circuit of size at most $\lceil \frac{n}{2} \rceil$.

*Proof. *Somewhat surprisingly, the proof is much easier than the graphic case. Let $G$ be a graph such that $M$ is the cocycle matroid of $G$. For simplicity, we assume that $G$ is connected (there is an easy reduction to this case). Moreover, by taking a minimum counterexample, we may assume that each colour class has size exactly $2$. Since $M$ has rank $n-1$ and $2n$ elements, the graphic matroid of $G$ has rank $n+1$. By connectivity, $G$ has exactly $n+2$ vertices. Since there are only $n$ colours and each colour class has size $2$, there must be two vertices $x,y$ such that $\delta_G(x)$ and $\delta_G(y)$ (the set of edges incident to $x$ and $y$, respectively) are both rainbow. Because $\delta_G(x)$ and $\delta_G(y)$ are cuts of $G$, we are done unless $\deg_G(x), \deg_G(y) \geq \lceil \frac{n}{2} \rceil+1$. Since $4n=2|E(G)|=\sum_{v \in V(G)} \deg_G(v)$, it follows that \[\sum_{v \in V(G) \setminus \{x,y\}} \deg_G(v) \leq 3n-2.\]Therefore, some vertex $z \in V(G) \setminus \{x,y\}$ has degree at most $2$, which contradicts that $M$ is simple.

Since we now know that the $r=2$ case of Conjecture 4 holds for both graphic and cographic matroids, it is tempting to make the following conjecture.

**Conjecture 5.** Let $M$ be a simple rank-$(n-1)$ regular matroid and $c$ be a colouring of $E(M)$ with $n$ colours, where each colour class has size at least $2$. Then $M$ contains a rainbow circuit of size at most $\lceil \frac{n}{2} \rceil$.

A natural proof strategy would be to use Seymour’s decomposition theorem for regular matroids, but the decomposition step seems non-trivial. Nonetheless, we do suspect that Conjecture 5 is true.

Finally, we could be even more ambitious and conjecture that Conjecture 5 holds for all binary matroids. However, here is an example showing that Conjecture 5 fails for binary matroids.

**Theorem 3. **For each even integer $n \geq 6$, there exists a simple rank-$(n-1)$ binary matroid $M$ on $2n$ elements, and a colouring of $E(M)$ where each colour class has size $2$, such that all rainbow circuits of $M$ have size strictly greater than $\frac{n}{2}$.

*Proof. *Let $n \geq 6$ be even. For each $i \in \{1, \dots, n-1\}$, let $\mathbf{e}_i$ be the $i$th standard basis vector in $\mathbb{F}_2^{n-1}$. Let $\mathbf 0$ and $\mathbf 1$ be the all-zeros and all-ones vectors in $\mathbb{F}_2^{n-1}$, respectively. Let $M$ be the binary matroid represented by the following $2n$ vectors $\mathcal V$.

- $\mathbf{e}_i$, for $i = 1, \dots, n-1$;
- $\mathbf{e}_i+ \mathbf{e}_{i+1}$, for $i =1, \dots, n-2$;
- $\mathbf 1$, $\mathbf{1} + \mathbf{e}_{n-2}$, and $\mathbf{e}_1+ \mathbf{e}_{n-2}$.

We now specify the colouring, which is just a pairing of $\mathcal V$. For $i =1, \dots, n-3$, we pair $\mathbf{e}_i$ with $\mathbf{e}_i + \mathbf{e}_{i+1}$. Finally, we pair $\mathbf{e}_{n-2}$ with $\mathbf{e}_1+ \mathbf{e}_{n-2}$; $\mathbf{e}_{n-1}$ with $\mathbf{e}_{n-2}+\mathbf{e}_{n-1}$; and $\mathbf 1$ with $\mathbf{1} + \mathbf{e}_{n-2}$.

To illustrate, the case $n=6$ is given by the following matrix, where for our colour blind readers, column $i$ and column $6+i$ are the same colour for $i =1, \dots, 6$.

\[

\left( \begin{array}{@{}*{12}{c}@{}}

\textcolor{red}{1} & \textcolor{blue}{0} & \textcolor{green}{0} & \textcolor{magenta}{0} & \textcolor{purple}{0} & \textcolor{cyan}{1} & \textcolor{red}{1} & \textcolor{blue}{0} & \textcolor{green}{0} & \textcolor{magenta}{1} & \textcolor{purple}{0} & \textcolor{cyan}{1} \\

\textcolor{red}{0} & \textcolor{blue}{1} & \textcolor{green}{0} & \textcolor{magenta}{0} & \textcolor{purple}{0} & \textcolor{cyan}{1} & \textcolor{red}{1} & \textcolor{blue}{1} & \textcolor{green}{0} & \textcolor{magenta}{0} & \textcolor{purple}{0} & \textcolor{cyan}{1} \\

\textcolor{red}{0} & \textcolor{blue}{0} & \textcolor{green}{1} & \textcolor{magenta}{0} & \textcolor{purple}{0} & \textcolor{cyan}{1} & \textcolor{red}{0} & \textcolor{blue}{1} & \textcolor{green}{1} & \textcolor{magenta}{0} & \textcolor{purple}{0} & \textcolor{cyan}{1} \\

\textcolor{red}{0} & \textcolor{blue}{0} & \textcolor{green}{0} & \textcolor{magenta}{1} & \textcolor{purple}{0} & \textcolor{cyan}{1} & \textcolor{red}{0} & \textcolor{blue}{0} & \textcolor{green}{1} & \textcolor{magenta}{1} & \textcolor{purple}{1} & \textcolor{cyan}{0} \\

\textcolor{red}{0} & \textcolor{blue}{0} & \textcolor{green}{0} & \textcolor{magenta}{0} & \textcolor{purple}{1} & \textcolor{cyan}{1} & \textcolor{red}{0} & \textcolor{blue}{0} & \textcolor{green}{0} & \textcolor{magenta}{0} & \textcolor{purple}{1} & \textcolor{cyan}{1}

\end{array} \right)\]

We omit the proof that all rainbow circuits of $M$ have size strictly greater than $\frac{n}{2}$, but the curious reader can see [3].

**References.**

**[1] **Ron Aharoni, Matthew DeVos, and Ron Holzman. *Rainbow triangles and the Caccetta-Häggkvist conjecture. *J. Graph Theory, 92(4):347–360, 2019.

**[2]** Louis Caccetta and R. Häggkvist. *On minimal digraphs with given girth.* In Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congress. Numer., XXI, pages 181–187. Utilitas Math., Winnipeg, Man.,1978.

**[3] **Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, and Amanda Montejano. *Short rainbow cycles in graphs and matroids*. arxiv.org/abs/1806.00825

**[4] **Blair D. Sullivan. *A summary of problems and results related to the Caccetta-Häggkvist conjecture.* arxiv.org/abs/math/0605646

**[5] **Yahya Ould Hamidoune. *A note on minimal directed graphs with given girth. *J. Combin. Theory Ser. B, 43(3):343–348,1987.

**[6] **C. T. Hoàng and B. Reed. *A note on short cycles in digraphs. *Discrete Math., 66(1-2):103–107, 1987.