The maximum number of 10- and 12-cycles in a planar graph


Abstract in English

For a fixed planar graph $H$, let $operatorname{mathbf{N}}_{mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In the case when $H$ is a cycle, the asymptotic value of $operatorname{mathbf{N}}_{mathcal{P}}(n,C_m)$ is currently known for $min{3,4,5,6,8}$. In this note, we extend this list by establishing $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{10})sim(n/5)^5$ and $operatorname{mathbf{N}}_{mathcal{P}}(n,C_{12})sim(n/6)^6$. We prove this by answering the following question for $min{5,6}$, which is interesting in its own right: which probability mass $mu$ on the edges of some clique maximizes the probability that $m$ independent samples from $mu$ form an $m$-cycle?

Download