The maximum number of paths of even length in a planar graph

Abstract

For graphs \(G\) and \(H\), let \(N(G,H)\) be the number of unlabeled, not necessarily induced copies of \(H\) in \(G\), and let \(f(n,H)\) be the maximum of \(N(G,H)\) over all \(n\)-vertex planar graphs \(G\). Ghosh, Győri, Martin, Paulos, Salia, Xiao and Zamora conjectured that, for every fixed integer \(\ell\ge 2\), \[ f(n,P_{2\ell+1}) =4\ell\left(\frac{n}{\ell}\right)^{\ell+1}+O(n^\ell). \] We prove the conjecture, including the stated error term. Along the way, we also settle the Cox--Martin optimization conjecture.

9 pages