DMS Colloquium: Gregory Puleo

Speaker: Gregory Puleo

Title: A story about graph saturation

Abstract: The classical extremal problem in graph theory asks: given some graph \(H\), what is the largest number of edges in an \(n\)-vertex graph with no subgraph isomorphic to \(H\)? In this talk, we will discuss the saturation problem in graph theory, a variant on the classical extremal problem.  In contrast to the extremal problem, for which powerful general results are known, relatively little is known about graph saturation. While general upper bounds on the saturation number are known, a nontrivial lower bound has been elusive. Recently, Alex Cameron and I succeeded at proving a lower bound on the saturation number that is asymptotically sharp on a large class of graphs. I will discuss both the mathematical details of this result and the story of how it came to be.