论文标题
适用于比赛和三角形家庭的短彩虹周期
Short rainbow cycles for families of matchings and triangles
论文作者
论文摘要
由Aharoni [Rainbow Triangles和Cacccta-Häggkvist猜想，J。GraphTheory（2019）提出的著名Caccetta-Häggkvist的概括是任何家庭$ \ Mathcal {f _1，f_1，f_1，\ ldots，f_ ldots $ s y s y hast y hast y hasts y hast y hast y hast y hast y hasts y hasts in长度最多最多$ \ lceil \ frac {n} {k} \ rceil $。以色列J. Math在[彩虹循环中的彩虹循环。 （2023）]和[Caccetta-Häggkvist猜想的非均匀度和彩虹版本，暹罗J.离散数学。 （2023）]结果表明，如果所有集合都是尺寸2的匹配，或者全部都是三角形，则可以将其改进到$ O（\ log n）$。我们表明，在混合情况下，如果每个$ f_i $都是尺寸2或三角形的匹配，则情况也是如此。我们还研究了每种$ f_i $都是2号或单个边缘的匹配，或者每个$ f_i $都是三角形或单个边缘，在每种情况下，我们确定类型之间的阈值比例，除此之外，彩虹围墙从线性到对数。
A generalization of the famous Caccetta--Häggkvist conjecture, suggested by Aharoni [Rainbow triangles and the Caccetta-Häggkvist conjecture, J. Graph Theory (2019)], is that any family $\mathcal{F}=(F_1, \ldots,F_n)$ of sets of edges in $K_n$, each of size $k$, has a rainbow cycle of length at most $\lceil \frac{n}{k}\rceil$. In [Rainbow cycles for families of matchings, Israel J. Math. (2023)] and [Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture, SIAM J. Discrete Math. (2023)] it was shown that asymptotically this can be improved to $O(\log n)$ if all sets are matchings of size 2, or all are triangles. We show that the same is true in the mixed case, i.e., if each $F_i$ is either a matching of size 2 or a triangle. We also study the case that each $F_i$ is a matching of size 2 or a single edge, or each $F_i$ is a triangle or a single edge, and in each of these cases we determine the threshold proportion between the types, beyond which the rainbow girth goes from linear to logarithmic.
