























In 1984, Erdős conjectured that the number of pentagons in any triangle-free graph on $n$ vertices is at most $(n/5)^5$, which is sharp by the balanced blow-up of a pentagon. This was proved by Grzesik, and independently by Hatami, Hladký, Král', Norine and Razborov. As an extension of this result for longer cycles, we prove that for each odd $k\geq 7$, the balanced blow-up of $C_k$ (uniquely) maximises the number of $k$-cycles among $C_{k-2}$-free graphs on $n$ vertices, as long as $n$ is sufficiently large. We also show that this is no longer true if $n$ is not assumed to be sufficiently large. Our result strengthens results of Grzesik and Kielak who proved that for each odd $k\geq 7$, the balanced blow-up of $C_k$ maximises the number of $k$-cycles among graphs with a given number of vertices and no odd cycles of length less than $k$. We further show that if $k$ and $\ell$ are odd and $k$ is sufficiently large compared to $\ell$, then the balanced blow-up of $C_{\ell+2}$ does not asymptotically maximise the number of $k$-cycles among $C_{\ell}$-free graphs on $n$ vertices. This disproves a conjecture of Grzesik and Kielak.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。