Rainbow Cycles in Properly Edge-Colored Graphs

Abstract

We prove that every properly edge-colored n-vertex graph with average degree at least 32 ( log 5 n ) 2 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$32(\log 5n)<^>2$$\end{document} contains a rainbow cycle, improving upon the ( log n ) 2 + o ( 1 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\log n)<^>{2+o(1)}$$\end{document} bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least 10 5 k 3 n 1 + 1 / k \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$10<^>5 k<^>3 n<^>{1+1/k}$$\end{document} edges contains a rainbow 2k-cycle, which improves the previous bound 2 c k 2 n 1 + 1 / k \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2<^>{ck<^>2}n<^>{1+1/k}$$\end{document} obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erd & odblac;s-Simonovits supersaturation theorem for even cycles, which may be of independent interest.