Partite Saturation Problems

We look at several saturation problems in complete balanced blow‐ups of graphs. We let H [ n ] denote the blow‐up of H onto parts of size n and refer to a copy of H in H [ n ] as partite if it has one vertex in each part of H [ n ] . We then ask how few edges a subgraph G of H [ n ] can have such that G has no partite copy of H but such that the addition of any new edge from H [ n ] creates a partite H . When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in [5][M. Ferrara, 2014]. Our main result is to calculate this value for H = K 4when 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 H [ n ] 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.