2020/06/23 by Tao Jiang, Jie Ma, Jiang, Tao +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2006.13206
openalex publication_date 2020/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A well-known result of Verstraëte \citeV00 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 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,k≥ 2, there exist constants c1=c1(r) and c2=c2(r,k), such that every linear r-uniform hypergraph G with average degree d(G)≥ c1 k contains linear cycles of k consecutive even lengths, the shortest of which is at most 2\lceil ( log n)/(log (d(G)/k)-c2)\rceil. In particular, as an immediate corollary, we retrieve the current best known upper bound on the linear Turán number of Cr2k with improved coefficients. Furthermore, we show that for any fixed integers r≥ 3,k≥ 2, there exist constants c3=c3(r) and c4=c4(r) such that every n-vertex linear r-uniform graph with average degree d(G)≥ c3k, contains linear cycles of k consecutive lengths, the shortest of which has length at most 6\lceil (log n)/(log (d(G)/k)-c4) \rceil +6. Both the degree condition and the shortest length among the cycles guaranteed are best possible up to a constant factor.