Short rainbow cycles for families of matchings and triangles

被引:0
作者
Guo, He [1 ]
机构
[1] Umea Univ, Dept Math & Math Stat, S-90187 Umea, Sweden
关键词
generalized Caccetta-Haggkvist conjecture; rainbow girth; short rainbow cycles; GIRTH;
D O I
10.1002/jgt.23183
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A generalization of the famous Caccetta-Haggkvist conjecture, suggested by Aharoni, is that any family F = (F-1,..., F-n) of sets of edges in K-n, each of size k, has a rainbow cycle of length at most inverted right perpendicularn/kinverted left perpendicular. In works by the author with Aharoni and by the author with Aharoni, Berger, Chudnovsky, and Zerbib, 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, that is, 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.
引用
收藏
页码:325 / 336
页数:12
相关论文
共 39 条