Short rainbow cycles for families of matchings and triangles

arXiv2210.12243MaRDI QIDQ6414725FDOQ6414725

Authors: He Guo 

Publication date: 21 October 2022

Abstract: A generalization of the famous Caccetta--H"aggkvist conjecture, suggested by Aharoni cite{ADH2019}, is that any family $mathcalF=(F_1,ldots,F_n)$ of sets of edges in $K_n$, each of size $k$, has a rainbow cycle of length at most $lceilfracnkceil$. In cite{AharoniGuo, ABCGZ2022} it was shown that asymptotically this can be improved to $O(logn)$ 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.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

This page was built for publication: Short rainbow cycles for families of matchings and triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414725)