Speaker: Chris Cox
Title: The maximum number of paths and cycles in planar graphs
Abstract: What is the maximum number of copies of a graph $H$ that can
appear in an $n$-vertex planar graph? In this talk, we introduce a
general technique which can be used to bound this quantity in terms of
an optimization problem over weighted graphs. By using this technique,
we attain asymptotically tight bounds on the maximum number of $P_7$'s,
$C_6$'s and $C_8$'s in a planar graph. Additionally, we demonstrate the
strength of this technique by re-deriving the known asymptotics of
maximum number of $P_5$'s and $C_4$'s, showing that these two cases are
essentially trivial. This technique can theoretically be used to prove
asymptotically tight bounds on the maximum number of odd paths and even
cycles in a planar graph in general, but we'll leave that endeavor to
future researchers (maybe even you)!
(Joint work with Ryan Martin)