Short rainbow cycles in graphs and matroids

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 matroidsarxiv.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.

Relaunch and Online Talks

We hope all our readers are staying safe during these difficult times.  Since online content is increasingly important at the moment, we thought it would be a very apt time to relaunch Matroid Union.  Thus, we are very pleased to announce that Rutger CampbellRelinde JurriusRose McCarty, and Jorn van der Pol will be joining us as new Editors.  Please contact us if you would like to give a guest post.

Dillon Mayhew and Peter Nelson are retiring from Matroid Union, and we wish them the best in their post-Blog existence.  

In addition, we’re excited to announce a new online matroid theory seminar with talks scheduled weekly on Thursdays at 3pm ET (8pm BST, 7am Friday NZDT). The seminar begins next week, and the first talks will be:

April 16: James Oxley, The binary matroids with no odd circuits of size exceeding five
April 23: Dillon Mayhew, Definability and non-definability for classes of matroids
April 30: Nathan Bowler, Quasi-graphic matroids
May 7: Rudi Pendavingh, Counting valuated matroid types
 
The talks will be held on Zoom and are open for anyone to attend. Links and further details will be posted on the Matroid Union website shortly. 
 
The seminar is organized by Jim Geelen, Peter Nelson, and Rose McCarty. 

SiGMa 2017 Recap

The Workshop on Structure in Graphs and Matroids (SiGMa 2017) just wrapped up a few weeks ago in Waterloo.  This was a continuation of similar workshops organized by Bert Gerards in 20082010, and 2012 and by Stefan van Zwam and Rudi Pendavingh in 2014 and 2016.

I would like to thank Jim Geelen, Peter Nelson, Luke Postle, and Stefan van Zwam (the organizers of this year’s workshop) who did an excellent job in choosing the program and making sure everything ran smoothly.  They even helped fellow Matroid Union blogger Nathan Bowler overcome Canadian Visa issues in time to give his (very nice) plenary talk (thanks also go to Alan).

This year the workshop was held in commemoration of William T. Tutte, who would have turned 100 this year.  See here for a short biography of Professor Tutte.  Some matroid theorists may not be aware of Tutte’s extremely important contributions as a code breaker at Bletchley Park during the Second World War.  The C&O Department at Waterloo has also been hosting a Distinguished Lecture Series in honour of Tutte this summer.  Click on this link for the list of speakers and to watch the videos on YouTube. SiGMa 2017 also featured a rare conference dinner speech by Jim Geelen on Tutte’s work.

In case you were not able to attend, all the talks from SiGMa 2017 were recorded and are now viewable on the C&O Department’s YouTube Channel.  The overall quality of talks was very high.  I won’t bias you with all of my personal favourites, but for example, all the plenaries and Paul Seymour were excellent.

Polymath 12: Rota’s Basis Conjecture

Polymath 12 has just recently launched, and the topic is Rota’s Basis Conjecture!  See this guest post by Jan Draisma for information on Rota’s Basis Conjecture.

The polymath projects are a sort of mathematical experiment proposed by Tim Gowers to see if massively collaborative mathematics is possible.  The proposed proof proceeds via a sequence of public comments on a blog.  The general idea is to blurt out whatever idea comes into your head to allow for rapid public dissemination.

Polymath 12 is hosted by Timothy Chow and you can click here to follow the progress or to contribute.