How many copies of a fixed cycle, $C_k$, can a planar graph contain? This problem has been studied in the case of even cycles by Cox-Martin and Lv et al. In this talk, we extend their results to answer the question asymptotically for odd cycles with $k=5,7,9$ and give a bound which is tight up to a factor of $3/2$ for all larger odd cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass $\mu$ on the edges of some clique maximizes the probability that $k$ edges sampled independently from $\mu$ form either a cycle or a path?
Maximizing the number of odd cycles in a planar graph
Emily Heath, Iowa State UniversityAuthors: Ryan R. Martin, Chris Wells
2023 AWM Research Symposium
Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]