Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

Abstract

For a digraph $G$ and $v\in V(G)$, let ${\delta }^{+}(v)$ be the number of out-neighbors of $v$ in $G$. The Caccetta-Häggkvist conjecture states that for all $k\ge 1$, if $G$ is a digraph with $n=|V(G)|$ such that ${\delta }^{+}(v)\ge k$ for all $v\in V(G)$, then $G$ contains a directed cycle of length at most $\lceil n/k\rceil$. Aharoni proposed a generalization of this conjecture, that a simple edge-colored graph on $n$ vertices with $n$ color classes, each of size at least $k$, has a rainbow cycle of length at most $\lceil n/k\rceil$. Let us call $(\alpha ,\beta )$ \emph{triangular} if every simple edge-colored graph on $n$ vertices with at least $\alpha n$ color classes, each with at least $\beta n$ edges, has a rainbow triangle. Aharoni, Holzman, and DeVos showed the following: $(9/8,1/3)$ is triangular; $(1,2/5)$ is triangular. In this paper, we improve those bounds, showing the following: $(1.1077,1/3)$ is triangular; $(1,0.3988)$ is triangular. Our methods give results for infinitely many pairs $(\alpha ,\beta )$, including $\beta <1/3$; we show that $(1.3481,1/4)$ is triangular.

Accepted manuscript; see DOI for journal version