2022/11/07 by Jaehoon Kim, Kim, Jaehoon, Joonkyung Lee +5 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Advanced Topology and Set Theory
paper · pdf · doi:10.48550/arxiv.2211.03291
We prove that every properly edge-colored n-vertex graph with average degree at least 100(log n)2 contains a rainbow cycle, improving upon (log n)2+o(1) bound due to Tomon. We also prove that every properly colored n-vertex graph with at least 105 k2 n1+1/k edges contains a rainbow 2k-cycle, which improves the previous bound 2ck2n1+1/k obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erdős--Simonovits supersaturation theorem for even cycles, which may be of independent interest.