{"id":2541,"date":"2020-06-02T11:17:57","date_gmt":"2020-06-02T15:17:57","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2541"},"modified":"2020-06-03T00:35:24","modified_gmt":"2020-06-03T04:35:24","slug":"short-rainbow-cycles-in-graphs-and-matroids","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2541","title":{"rendered":"Short rainbow cycles in graphs and matroids"},"content":{"rendered":"\n

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

Conjecture 1 <\/strong>(Caccetta and H\u00e4ggkvist [2]).\u00a0 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$.<\/p>\n

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

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

Conjecture<\/strong> 2<\/strong>\u00a0<\/strong>(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$.<\/p>\n

Here,\u00a0rainbow<\/em> means that no two edges of the cycle are the same colour.\u00a0 Note that\u00a0 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.\u00a0 \u00a0<\/p>\n

We now show that the following weakening of Aharoni’s conjecture still implies the Caccetta-H\u00e4ggkvist conjecture.<\/p>\n

Conjecture 3<\/strong>. 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$.<\/p>\n

Proof of the implication. <\/em>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.\u00a0 Moreover, colour each edge $ij$ of $G$ with colour $i$ if $(i,j)$ is an arc of $D$.\u00a0 Clearly, this colouring uses $n$ colours.\u00a0 Since $D$ has minimum outdegree at least $r$, each colour class has size at least $r$.\u00a0 By Conjecture 3, $G$ contains a properly edge-coloured cycle $C$ of length at most $\\lceil \\frac{n}{r} \\rceil$.\u00a0 Since $C$ is properly edge-coloured, $C$ must correspond to a directed cycle in $D$.\u00a0\u00a0<\/p>\n

Unlike the Caccetta-H\u00e4ggkvist conjecture, Aharoni’s conjecture has a very natural matroid generalization.\u00a0 Since this is a matroid blog, this is a good thing.\u00a0 \u00a0All notions in Aharoni’s conjecture easily carry over to matroids, except possibly the number of vertices $n$ of $G$.\u00a0 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$.\u00a0 \u00a0\u00a0<\/p>\n

Conjecture 4.<\/strong>\u00a0 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$.<\/p>\n

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

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

Theorem 1.\u00a0 <\/strong>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$.<\/p>\n

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

Equivalently, Theorem 1 shows that Conjecture 4 holds for graphic matroids when $r=2$.\u00a0 We now show that this is also true for cographic matroids.\u00a0\u00a0<\/p>\n

Theorem 2.<\/strong> 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$.<\/p>\n

Proof.\u00a0<\/em>Somewhat surprisingly, the proof is much easier than the graphic case.\u00a0 Let $G$ be a graph such that $M$ is the cocycle matroid of $G$.\u00a0 For simplicity, we assume that $G$ is connected (there is an easy reduction to this case).\u00a0 Moreover, by taking a minimum counterexample, we may assume that each colour class has size exactly $2$.\u00a0 Since $M$ has rank $n-1$ and $2n$ elements, the graphic matroid of $G$ has rank $n+1$.\u00a0 By connectivity, $G$ has exactly $n+2$ vertices.\u00a0 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)$\u00a0 (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.\u00a0<\/p>\n

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.\u00a0\u00a0<\/p>\n

Conjecture 5.<\/strong>\u00a0 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$.<\/p>\n

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

Finally, we could be even more ambitious and conjecture that Conjecture 5 holds for all binary matroids.\u00a0 However, here is an example showing that Conjecture 5 fails for binary matroids.\u00a0\u00a0<\/p>\n

Theorem 3.\u00a0<\/strong>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}$.<\/p>\n

Proof.\u00a0 <\/em>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$.<\/p>\n