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\).