Saturation numbers of bipartite graphs in random graphs

Abstract

For a given graph $F$, the $F$-saturation number of a graph $G$, denoted by $sat(G,F)$, is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. In 2017, Korándi and Sudakov determined $sat(G(n,p),K_r)$ asymptotically, where $G(n,p)$ denotes the Erdős-Rényi random graph and $K_r$ is the complete graph on $r$ vertices. In this paper, among other results, we present an asymptotic upper bound on $sat(G(n,p),F)$ for any bipartite graph $F$ and also an asymptotic lower bound on $sat(G(n,p),F)$ for any complete bipartite graph $F$.