Seminar: Saturation in deterministic and random graphs

Speaker: Behruz Tayfeh-Rezaie, Institute for Research in Fundamental Sciences (IPM), Iran

Title: Saturation in deterministic and random graphs

Abstract: 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 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 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.