Maximizing the number of odd cycles in a planar graph

Abstract: 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?

Back to Search Research Symposium Abstracts