Score: 0

Short rainbow cycles for families of small edge sets

Published: July 6, 2025 | arXiv ID: 2507.04581v1

By: He Guo

Potential Business Impact:

Finds short, colorful loops in math puzzles.

Business Areas:
Cycling Sports

In 2019, Aharoni proposed a conjecture generalizing the Caceetta-H\"aggkvist conjecture: if an $n$-vertex graph $G$ admits an edge coloring (not necessarily proper) with $n$ colors such that each color class has size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil n/r\rceil$. Recent works \cite{AG2023,ABCGZ2023,G2025} have shown that if a constant fraction of the color classes are non-star, then the rainbow girth is $O(\log n)$. In this note, we extend these results, and we show that even a small fraction of non-star color classes suffices to ensure logarithmic rainbow girth. We also prove that the logarithmic bound is of the right order of magnitude. Moreover, we determine the threshold fraction between the types of color classes at which the rainbow girth transitions from linear to logarithmic.

Country of Origin
πŸ‡ΈπŸ‡ͺ Sweden

Page Count
9 pages

Category
Mathematics:
Combinatorics