The Extremal Function for Cycles of Length l mod k
The Extremal Function for Cycles of Length l mod k
复制标题
DOI：
10.37236/6257
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
B. Sudakov;Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
B. Sudakov;Jacques Verstraëte
Burr和Erd \H{o}推测，对于每个$k,\ell \in \mathbb Z^+$，使得$k \mathbb Z + \ell$包含偶数，存在$c_k(\ell)$，使得任何平均度至少$c_k(\ell)$的图包含一个长度为$\ell$ mod $k$的循环。这个猜想由Bollobás证明，文献中出现了许多关于$c_k(\ell)$上界的连续改进。在这个简短的说明中，对于$1 \leq \ell \leq k$，我们表明$c_k(\ell)$与$k$顶点上的$C_{\ell}$自由图的最大平均度成正比，这决定了$c_k(\ell)$直到一个绝对常数。特别地，使用已知的关于Turán偶数循环的结果，我们得到$c_k(\ell) = O(\ell k^{2/\ell})$对于所有的偶数$\ell$，这对于$\ell \in \{4,6,10\}$是紧的。由于完全二部图$K_{\ell - 1,n - \ell + 1}$没有长度为$2\ell$ mod $k$的循环，因此对于$\ell = \Omega(\log k)$也显示了$c_k(\ell) = \Theta(\ell)$。
Burr and Erd\H{o}s conjectured that for each $k,\ell \in \mathbb Z^+$ such that $k \mathbb Z + \ell$ contains even integers, there exists $c_k(\ell)$ such that any graph of average degree at least $c_k(\ell)$ contains a cycle of length $\ell$ mod $k$. This conjecture was proved by Bollob\'{a}s, and many successive improvements of upper bounds on $c_k(\ell)$ appear in the literature. In this short note, for $1 \leq \ell \leq k$, we show that $c_k(\ell)$ is proportional to the largest average degree of a $C_{\ell}$-free graph on $k$ vertices, which determines $c_k(\ell)$ up to an absolute constant. In particular, using known results on Tur\'{a}n numbers for even cycles, we obtain $c_k(\ell) = O(\ell k^{2/\ell})$ for all even $\ell$, which is tight for $\ell \in \{4,6,10\}$. Since the complete bipartite graph $K_{\ell - 1,n - \ell + 1}$ has no cycle of length $2\ell$ mod $k$, it also shows $c_k(\ell) = \Theta(\ell)$ for $\ell = \Omega(\log k)$.