论文标题
彩虹循环在适当的边彩图中
Rainbow cycles in properly edge-colored graphs
论文作者
论文摘要
我们证明，每个适当的边缘颜色$ n $ vertex图，平均度至少$ 100（\ log n）^2 $包含一个彩虹循环，在$（\ log n）^{2+o（1）} $上改善了由于tomon而绑定的。我们还证明，每个正确颜色的$ n $ vertex图都至少为$ 10^5 k^2 n^{1+1/k} $边缘包含一个彩虹$ 2K $ -CYCLE，这改善了以前的绑定$ 2^{CK^2} n^n^{1+1+1/k} $。 我们使用同态不平等和不平衡的正则化引理的方法也提供了一种简单的方法来证明ERDőS-simonovits Suimonovits对于偶数循环的超饱和定理，这可能具有独立的利益。
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 $10^5 k^2 n^{1+1/k}$ edges contains a rainbow $2k$-cycle, which improves the previous bound $2^{ck^2}n^{1+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.
