A sharp asymptotic bound for odd cycles in planar graphs

Abstract

For graphs $G$ and $H$, let $\mathbf{N}(G,H)$ denote the number of unlabeled, not necessarily induced copies of $H$ in $G$, and let ${\mathbf{N}}_{\mathcal{P}}(n,H)$ be the maximum of $\mathbf{N}(G,H)$ over all $n$-vertex planar graphs $G$. We prove that, for every fixed integer $m\ge 3$, \[ \mathbf{N}_{\mathcal P}(n,C_{2m+1}) =2m\left(\frac{n}{m}\right)^m +O_m\!\left(n^{m-1/5}\right). \] Heath, Martin, and Wells reduced the determination of the leading term to a weighted optimization conjecture involving cycles and paths. We prove a stronger sharp cycle--path inequality for probability weights on the edges of a complete graph and characterize equality in their conjectured inequality. Together with their reduction lemma, this settles the conjecture and yields the formula above, including the stated error term. The cases $m\ge 5$ are new; combined with the known results for $C_3$ and $C_5$, this determines the leading term for every fixed odd cycle in planar graphs.

9 pages