Minimum Saturated Graphs and Hypergraphs

Oleg Pikhurko
Carnegie-Mellon University

A (hyper)graph $G$ is \textit{$F$-saturated} if $G$ is $F$-free but the addition of any new edge creates a copy of $F$. Let $sat(n,F)$ be the smallest size of an $F$-saturated graph of order $n$.

I will survey this area and present a recent result with Tom Bohman and Maria Fonoberova, where we determine the sat-function for an arbitrary complete partite graph $F$ within additive error $O(1)$.


Back to Workshop III: Topics in Graphs and Hypergraphs