Weak saturation numbers of complete bipartite graphs in the clique

The notion of weak saturation was introduced by Bollobas in 1968. Let F and H be graphs. A spanning subgraph G subset of F is weakly (F, H)-saturated if it contains no copy of H but there exists an ordering e1, ..., e(t) of E(F) \ E(G) such that for each i is an element of [t], the graph G boolean OR {e(1), ..., e(i)} contains a copy H' of H such that e(i) is an element of H'. Define wsat(F, H) to be the minimum number of edges in a weakly (F, H)-saturated graph. In this paper, we prove for all t >= 2 and n >= 3t - 3, that wsat(K-n, K-t,K-t) = (t - 1)(n + 1- t/2), and we determine the value of wsat(K-n, K-t-1,K-t) as well. For fixed 2 <= s < t, we also obtain bounds on wsat(K-n, K-s,K-t) that are asymptotically tight. (C) 2020 Elsevier Inc. All rights reserved.