Counting paths, cycles, and blow‐ups in planar graphs

For a planar graphH $H$ , letN P ( n , H )${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ denote the maximum number of copies ofH $H$ in ann $n$ ‐vertex planar graph. In this paper, we prove thatN P ( n , P 7 ) ~ 4 27 n 4${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{7})\unicode{x0007E}\frac{4}{27}{n}^{4}$ ,N P ( n , C 6 ) ~ ( n ∕ 3 ) 3${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{6})\unicode{x0007E}{(n\unicode{x02215}3)}^{3}$ ,N P ( n , C 8 ) ~ ( n ∕ 4 ) 4${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{8})\unicode{x0007E}{(n\unicode{x02215}4)}^{4}$ , andN P ( n , K 4 { 1 } )~( n ∕ 6 ) 6${{\bf{N}}}_{{\mathscr{P}}}(n,{K}_{4}\{1\})\,\unicode{x0007E}\,{(n\unicode{x02215}6)}^{6}$ , whereK 4 { 1 }${K}_{4}\{1\}$ is the 1‐subdivision ofK 4${K}_{4}$ . In addition, we obtain significantly improved upper bounds onN P ( n , P 2 m + 1)${{\bf{N}}}_{{\mathscr{P}}}(n,{P}_{2m+1})$ andN P ( n , C 2 m)${{\bf{N}}}_{{\mathscr{P}}}(n,{C}_{2m})$ form ≥ 4 $m\ge 4$ . For a wide class of graphsH $H$ , the key technique developed in this paper allows us to boundN P ( n , H )${{\bf{N}}}_{{\mathscr{P}}}(n,H)$ in terms of an optimization problem over weighted graphs.