Short rainbow cycles in graphs and matroids.

Let G be a simple n‐vertex graph and c be a coloring of E(G) with n colors, where each color class has size at least 2. We prove that (G,c) contains a rainbow cycle of length at most ⌈n2⌉, which is best possible. Our result settles a special case of a strengthening of the Caccetta‐Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids. [ABSTRACT FROM AUTHOR]