DMS Combinatorics Seminar

Speaker: Chris Cox, Iowa State University

Title: Subgraph counts in planar graphs and maximum likelihood estimators of graphs

Abstract:
(1) How many copies of a graph $H$ can exist within an $n$-vertex planar graph? Such questions can be traced back to the late 1970's when Hakimi and Schmeichel determined the maximum number of copies of $C_3$ and $C_4$ that a planar graph can hold. Furthermore, these problems have recently regained quite a bit of popularity!

(2) For a graph $H$ on $m$ edges, which probability mass $\mu$ on the edges of some clique maximizes the probability that $m$ edges sampled independently from $\mu$ form a copy of $H$? While maximum likelihood estimation questions have a rich history (dating back to the 1920's), the above question appears to have never been asked...

It turns out that there's a close relationship between problems (1) and (2) for graphs which display a certain subdivision structure. In this talk, we'll discuss this relationship illustrate how it can be used to show that a planar graph on $n$ vertices contains at most $(n/3)^3$ many copies of $C_6$.