Weak saturation numbers of large complete bipartite graphs

Abstract

An $n$-vertex graph $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ and there exists an ordering of all edges in $E(K_n)\setminus E(G)$ such that, when added one at a time, each edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ is called the weak saturation number $\mathrm{wsat}(n,F)$. We obtain exact values and new bounds for $\mathrm{wsat}(n,K_{s,t})$ in the previously unaddressed range $s+t<n<3t-3$, where $3\le s\le t$. To prove lower bounds, we introduce a new method that takes into account connectivity properties of subgraphs of a complement $G^{\prime }$ to a weakly saturated graph $G$. We construct an auxiliary hypergraph and show that a linear combination of its parameters always increases in the process of the deletion of edges of $G^{\prime }$. This gives a lower bound which is tight, up to an additive constant.