School of Mathematical Sciences

I Can't Get No Saturation menu

I Can't Get No Saturation

Natalie Behague
Tue, 07/11/2017 - 12:00

What does saturation mean in the context of graph theory? We say a big graph G is saturated with a small graph F if the graph G doesn't contain a copy of F, but adding any edge to G creates a copy of F. A lot is known about the maximum number of edges a saturated graph can have, but what about the minimum number of edges? It turns out this number is a slippery beast, and I'll talk about why. And then, because why not, we'll see if we can generalise these ideas to hypergraphs.