Lethbridge Number Theory and Combinatorics Seminar: Behruz Tayfeh-Rezaie
Topic
Saturation in deterministic and random graphs
Speakers
Details
Fix a positive integer and a graph . A graph with vertices is called -saturated if contains no subgraph isomorphic to but each graph obtained from by joining a pair of nonadjacent vertices contains at least one copy of as a subgraph. The saturation function of , denoted , is the minimum number of edges in an -saturated graph on vertices. This parameter along with its counterpart, i.e. Turan number, have been investigated for quite a long time.
We review known results on for various graphs . We also present new results when is a complete multipartite graph or a cycle graph. The problem of saturation in the Erdos-Renyi random graph 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.