Partite Saturation Problems

We look at several saturation problems in complete balanced blow‐ups of graphs. We let denote the blow‐up of H onto parts of size n and refer to a copy of H in as partite if it has one vertex in each part of . We then ask how few edges a subgraph G of can have such that G has no partite copy of H but such that the addition of any new edge from creates a partite H. When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in  5 . Our main result is to calculate this value for when n is large. We also give exact results for paths and stars and show that for 2‐connected graphs the answer is linear in n whilst for graphs that are not 2‐connected the answer is quadratic in n. We also investigate a similar problem where G is permitted to contain partite copies of H but we require that the addition of any new edge from creates an extra partite copy of H. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.