论文标题
阿哈罗尼（Aharoni）彩虹概括的三角形案例的界限改善了cacceta-häggkvist猜想
Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
论文作者
论文摘要
对于v（g）$中的digraph $ g $和$ v \，令$δ^+（v）$是$ g $中$ v $的超近伯爵的数量。 caccetta-häggkvist的猜想指出，对于所有$ k \ ge 1 $，如果$ g $是$ n = | v（g）| $的digraph，则$Δ^+（v）\ ge k $ for v（g）$ in v（g）$，则$ g $，然后包含一个最大的$ \ lceil n/k k \ rce n/k k \ rceil $ rce n/k \ rce。 Aharoni提出了对此猜想的概括，即具有$ N $颜色类的$ N $顶点上的简单边彩图，每个大小至少$ k $，最多具有$ \ lceil n/k \ rceil $的彩虹周期。让我们称呼$（α，β）$ \ emph {三角形}，如果在$ n $ dertices上的每个简单的边彩色图具有至少$αn$颜色类别，每个颜色级别至少具有$βn$边缘，都有一个彩虹三角形。 Aharoni，Holzman和Devos显示了以下内容：$（9/8,1/3）$是三角形的； $（1,2/5）$是三角形。在本文中，我们提高了这些界限，显示以下内容：$（1.1077,1/3）$是三角形的； $（1,0.3988）$是三角形。我们的方法给出了无限多对$（α，β）$的结果，包括$β<1/3 $；我们表明$（1.3481,1/4）$是三角形的。
For a digraph $G$ and $v \in V(G)$, let $δ^+(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 $δ^+(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 $(α, β)$ \emph{triangular} if every simple edge-colored graph on $n$ vertices with at least $αn$ color classes, each with at least $β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 $(α, β)$, including $β< 1/3$; we show that $(1.3481,1/4)$ is triangular.
