Counting paths, cycles and blow-ups in planar graphs

Abstract

For a planar graph $H$, let $N_{\mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In this paper, we prove that $N_{\mathcal{P}}(n,P_7)\sim \frac{4}{27}{n}^4$, $N_{\mathcal{P}}(n,C_6)\sim (n/3{)}^3$, $N_{\mathcal{P}}(n,C_8)\sim (n/4{)}^4$ and $N_{\mathcal{P}}(n,K_4\{1\})\sim (n/6{)}^6$, where $K_4\{1\}$ is the $1$-subdivision of $K_4$. In addition, we obtain significantly improved upper bounds on $N_{\mathcal{P}}(n,P_{2m+1})$ and $N_{\mathcal{P}}(n,C_{2m})$ for $m\ge 4$. For a wide class of graphs $H$, the key technique developed in this paper allows us to bound $N_{\mathcal{P}}(n,H)$ in terms of an optimization problem over weighted graphs.

arXiv comment30 pages