Bounding the number of odd paths in planar graphs via convex optimization

Let $N_{\mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$ vertex planar graph. The problem of bounding this function for various graphs $H$ has been extensively studied since the 70’s. A special case that received a lot of attention recently is when $H$ is the path on $2m+1$ vertices, denoted $P_{2m+1}$. Our main result in this paper is that $$N_{\mathcal{P}}(n,P_{2m+1})=O(m^{-m}{n}^{m+1})\mathrm{.}$$ This improves upon the previously best known bound by a factor $e^m$, which is best possible up to the hidden constant, and makes a significant step towards resolving conjectures of Gosh et al. and of Cox and Martin. The proof uses graph theoretic arguments together with (simple) arguments from the theory of convex optimization.