Counting even cycles and even paths with bounded circumference

Summary · qwen2.5:32b

The study proves sharp extremal results for the number of even cycles $C_{2s}$ and even paths $P_{2r+1}$ in graphs without long cycles, verifying a conjecture on $\mathrm{ex}(n,C_k,C_{\ge L+1})$ for even cycles and providing exact counts for even paths with bounded circumference. Specifically, for even cycles of length at least $L+1$, the extremal number equals $C_{2s}(H(n,L))$ for large $n$.

Suggested post angle

This article discusses counting even cycles and paths with bounded circumference, which involves concepts related to graph theory and mathematics. It could be of interest to those following research in rendering (due to its graphic nature) or math.

Excerpt

arXiv:2607.04357v1 Announce Type: new Abstract: For an integer $L$, write $C_{\ge L}$ for the family of cycles of length at least $L$. For $L=2a$ let $H(n,L)=K_a+\overline K_{n-a}$, and for $L=2a+1$ let $H(n,L)$ be obtained from $K_a+\overline K_{n-a}$ by adding one edge inside the independent part. We prove sharp results for two even target graphs, namely even cycles $C_{2s}$ and even paths $P_{2r+1}$. For even cycles, with $s\ge3$ and $L\ge2s$, we have \[ \mathrm{ex}(n,C_{2s},C_{\ge L+1})=C_{2s}(H(n,L)) \] for all sufficiently large $n$. Together with the known $C_4$ case of Zhu, Gy\H{o}ri, He, Lv, Salia and Xiao~[Bull. Lond. Math. Soc. 55 (2023)], this verifies the even-cycle case of their conjecture on $\mathrm{ex}(n,C_k,C_{\ge L+1})$. For even paths, with $r\ge2$ and $L\ge2r$, we have \[ \mathrm{ex}(n,P_{2r+1},C_{\ge L+1})=N(P_{2r+1},H(n,L)) \] for all sufficiently large $n$. We also derive the corresponding exact results when the forbidden graph is a path $P_{p+1}$, sharpening the relevant even-cycle and even-path asymptotic results of Gy\H{o}ri, Salia, Tompkins and Zamora~[Discrete Math. Theor. Comput. Sci. 21 no. 1 (2019)].