论文标题
循环的广义彩虹图兰问题
The generalised rainbow Turán problem for cycles
论文作者
论文摘要
鉴于边缘彩色的图，我们说如果其所有边缘都有不同的颜色，则是彩虹。令$ \ operatorname {ex}（n，h，$ rainbow-$ f）$表示$ h $的最大副本数量，如果$ n $ vertices上的适当边缘色的图形可以包含，如果它没有彩虹子图与$ f $。我们确定$ \ operatorname {ex}（n，c_s，$ rainbow- $ c_t）$的数量级，所有$ s，t $ at $ s \ not = 3 $。特别是，我们通过证明$ \ operatorName {ex}（n，c_ {2k}，$ rainbow- $ c_ {2k}）$是$θ（n^{k-1} $ k \ geq 3 $和$θ（$ k = $ th），我们将回答Gerbner，Mészáros，Methuku和Palmer的问题。我们还确定了$ \ operatatorName {ex}的数量级（n，p_ \ ell，$ rainbow- $ c_ {2k}）$ for All $ k，\ ell \ geq 2 $，其中$ p_ \ ell $表示$ \ ell $ edges的路径。
Given an edge-coloured graph, we say that a subgraph is rainbow if all of its edges have different colours. Let $\operatorname{ex}(n,H,$rainbow-$F)$ denote the maximal number of copies of $H$ that a properly edge-coloured graph on $n$ vertices can contain if it has no rainbow subgraph isomorphic to $F$. We determine the order of magnitude of $\operatorname{ex}(n,C_s,$rainbow-$C_t)$ for all $s,t$ with $s\not =3$. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer by showing that $\operatorname{ex}(n,C_{2k},$rainbow-$C_{2k})$ is $Θ(n^{k-1})$ if $k\geq 3$ and $Θ(n^2)$ if $k=2$. We also determine the order of magnitude of $\operatorname{ex}(n,P_\ell,$rainbow-$C_{2k})$ for all $k,\ell\geq 2$, where $P_\ell$ denotes the path with $\ell$ edges.
