Saturation in deterministic and random graphs

Fix a positive integer $n$ and a graph $F$. A graph $G$ with $n$ vertices is called $F$-saturated if $G$ contains no subgraph isomorphic to $F$ but each graph obtained from $G$ by joining a pair of nonadjacent vertices contains at least one copy of $F$ as a subgraph. The saturation function of $F$, denoted $\mathrm{sat}(n, F)$, is the minimum number of edges in an $F$-saturated graph on $n$ vertices. This parameter along with its counterpart, i.e. Turan number, have been investigated for quite a long time.

We review known results on $\mathrm{sat}(n, F)$ for various graphs $F$. We also present new results when $F$ is a complete multipartite graph or a cycle graph. The problem of saturation in the Erdos-Renyi random graph $G(n, p)$ was introduced by Korandi and Sudakov in 2017. We survey the results for random case and present our latest results on saturation numbers of bipartite graphs in random graphs.