Linear cycles of consecutive lengths
Linear cycles of consecutive lengths
复制标题
DOI：
10.1016/j.jctb.2023.06.002
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
T. Jiang;Jie Ma;Liana Yepremyan
中科院分区：
文献类型：
--
作者：
T. Jiang;Jie Ma;Liana Yepremyan
Verstraëte [23] 的一个众所周知的结果表明，对于每个整数 k≥ 2，每个平均度数至少为 8k 的图 G 都包含 k 个连续偶数长度的循环，其中最短的长度最多为 G 半径的两倍。我们建立了 Verstraëte 结果的两个扩展，用于线性 r 均匀超图中的线性循环。我们证明，对于任何固定整数 r≥ 3 和 k≥ 2，存在常数 c 1= c 1 (r) 和 c 2= c 2 (r)，使得每个平均度为 d (G)≥ c 1 k 的 n 顶点线性 r 均匀超图 G 包含 k 个连续偶数长度的线性循环，其中最短的长度至多为 2⌈ log n log(d (G)/k)− c 2⌉。特别是，作为直接推论，我们使用改进的系数检索了 C 2 k r 的线性 Turán 数的当前最著名的上限。此外，我们证明，对于任何固定整数 r≥ 3 和 k≥ 2，存在常数 c 3= c 3 (r) 和 c 4= c 4 (r)，使得每个平均度 d (G)≥ c 3 k 的 n 顶点线性 r 均匀超图包含 k 个连续长度的线性循环，其中最短的长度至多 6⌈ log n log(d (G)/k)− c 4⌉+ 6. 在这两种情况下，对于给定的平均度数 d，最短周期的长度不能提高到常数因子 c 2、c 4。
A well-known result of Verstraëte [23] shows that for each integer k≥ 2 every graph G with average degree at least 8k contains cycles of k consecutive even lengths, the shortest of which is of length at most twice the radius of G. We establish two extensions of Verstraëte's result for linear cycles in linear r-uniform hypergraphs. We show that for any fixed integers r≥ 3 and k≥ 2, there exist constants c 1= c 1 (r) and c 2= c 2 (r), such that every n-vertex linear r-uniform hypergraph G with average degree d (G)≥ c 1 k contains linear cycles of k consecutive even lengths, the shortest of which is of length at most 2⌈ log n log(d (G)/k)− c 2⌉. In particular, as an immediate corollary, we retrieve the current best known upper bound on the linear Turán number of C 2 k r with improved coefficients. Furthermore, we show that for any fixed integers r≥ 3 and k≥ 2, there exist constants c 3= c 3 (r) and c 4= c 4 (r) such that every n-vertex linear r-uniform hypergraph with average degree d (G)≥ c 3 k, contains linear cycles of k consecutive lengths, the shortest of which has length at most 6⌈ log n log(d (G)/k)− c 4⌉+ 6. In both cases for given average degree d, the length of the shortest cycles cannot be improved up to the constant factors c 2, c 4.