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.