PreprintarXiv licencearXiv
Generalized Turán problems for shorter even cycles
Abstract
For graphs H and F, let ex(n,H,F) denote the maximum number of copies of H in an n-vertex F-free graph. Gerbner, Győri, Methuku, and Vizer proved that ex(n,C2ℓ,C2k)=Θ(nℓ) for k>ℓ≥2. They determined the leading term for ℓ=2, but for k>ℓ≥3 their general lower and upper bounds had different leading constants, leaving open the problem of closing this gap. We solve this problem by showing that, for every k>ℓ≥2, ex(n,C2ℓ,C2k)=(((k−1)ℓ)/2ℓ+o(1))nℓ, where (k−1)ℓ=(k−1)(k−2)⋯(k−ℓ).
Related
- Balanced even cycles in signed graphs:Turán bounds, double covers, and parity obstructions
- NP-Hardness of Generalized-Turán Graph Modification Problems
- NP-hardness of additive approximation for generalized Turán problems
- Extremal problems for suspensions of even cycles
- Spectral Generalized Turán Problems for Expansion Hypergraphs
BibTeX
@misc{liu2026generalized,
title = {{Generalized Turán problems for shorter even cycles}},
author = {Zhen Liu and Chuanshu Wu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37376},
eprint = {2609.37376},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37376},
}
RIS
TY - UNPB
TI - Generalized Turán problems for shorter even cycles
AU - Zhen Liu
AU - Chuanshu Wu
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37376
UR - https://arxiv.org/abs/2609.37376
AB - For graphs H and F, let ex(n,H,F) denote the maximum number of copies of H in an n-vertex F-free graph. Gerbner, Győri, Methuku, and Vizer proved that ex(n,C_2ℓ,C_2k)=Θ(n^ℓ) for k>ℓ≥2. They determined the leading term for ℓ=2, but for k>ℓ≥3 their general lower and upper bounds had different leading constants, leaving open the problem of closing this gap. We solve this problem by showing that, for every k>ℓ≥2, ex(n,C_2ℓ,C_2k)=(((k−1)_ℓ)/2ℓ+o(1))n^ℓ, where (k−1)_ℓ=(k−1)(k−2)⋯(k−ℓ).
ER -