论文标题
彩虹图恩数量的偶数循环，重复的模式和周期的爆炸
Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
论文作者
论文摘要
图$ h $的RainbowTurán编号$ \ mathrm {ex}^*（n，h）$是适当边缘色的$ n $ vertex图中最大可能的边数，没有彩虹子级同构为$ h $。我们证明，对于任何整数$ k \ geq 2 $，$ \ mathrm {ex}^*（n，c_ {2k}）= o（n^{1+1/k}）$。这很紧，并建立了Keevash，Mubayi，Sudakov和Verstraëte的猜想。我们使用相同的方法来证明各种主题中的其他一些猜想。首先，我们证明存在一个常数的$ c $，因此任何适当的边缘色$ n $ vertex图具有超过$ cn（\ log n）^4 $边缘包含彩虹循环。众所周知，存在$ω（n \ log n）$边缘的正确边缘$ n $ vertex图，不包含任何彩虹循环。其次，我们表明，在$ o（n^{\ frac {r} {r-1} {r-1} \ cdot \ frac \ frac {k-1} {k-1}}}）$的任何适当的边缘色中，存在$ r $ r $ colour-iSomorphic，pairour-isomorphic，paighwise pertex-disex-joint copies $ c__} $。这证明了强烈的猜想是Conlon和Tyomkyn的猜想，以及Xu，Zhang，Jing和GE提出的Strenghtenten版本。此外，我们通过证明存在常数的$ c = c（r）$，以使任何$ n $ vertex图具有超过$ cn^{2-1/r}（\ log n）^{7/r} $ edges包含一个均匀周期的$ r $ blowup。最后，我们证明了$ c_ {2k} $的$ r $ -blowupturán数字$ o（n^{2- \ frac {1} {r} {r}+\ frac {1} {k+r-1}+r-1}+o（1）}）
The rainbow Turán number $\mathrm{ex}^*(n,H)$ of a graph $H$ is the maximum possible number of edges in a properly edge-coloured $n$-vertex graph with no rainbow subgraph isomorphic to $H$. We prove that for any integer $k\geq 2$, $\mathrm{ex}^*(n,C_{2k})=O(n^{1+1/k})$. This is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstraëte. We use the same method to prove several other conjectures in various topics. First, we prove that there exists a constant $c$ such that any properly edge-coloured $n$-vertex graph with more than $cn(\log n)^4$ edges contains a rainbow cycle. It is known that there exist properly edge-coloured $n$-vertex graphs with $Ω(n\log n)$ edges which do not contain any rainbow cycle. Secondly, we show that in any proper edge-colouring of $K_n$ with $o(n^{\frac{r}{r-1}\cdot \frac{k-1}{k}})$ colours, there exist $r$ colour-isomorphic, pairwise vertex-disjoint copies of $C_{2k}$. This proves in a strong form a conjecture of Conlon and Tyomkyn, and a strenghtened version proposed by Xu, Zhang, Jing and Ge. Moreover, we answer a question of Jiang and Newman by showing that there exists a constant $c=c(r)$ such that any $n$-vertex graph with more than $cn^{2-1/r}(\log n)^{7/r}$ edges contains the $r$-blowup of an even cycle. Finally, we prove that the $r$-blowup of $C_{2k}$ has Turán number $O(n^{2-\frac{1}{r}+\frac{1}{k+r-1}+o(1)})$, which can be used to disprove an old conjecture of Erd\H os and Simonovits.
