IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The maximum number of paths and cycles in planar graphs

  • Feb. 12, 2021
  • 2:30 p.m.

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)

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC