Exact Bounds for Some Hypergraph Saturation Problems

Let Wn(p, q) denote the minimum number of edges in an n × n bipartite graph G on vertex sets X,Y that satisfies the following condition; one can add the edges between X and Y that do not belong to G one after the other so that whenever a new edge is added, a new copy of Kp,q is created. The problem of bounding Wn(p, q), and its natural hypergraph generalization, was introduced by Balogh, Bollobás, Morris and Riordan. Their main result, specialized to graphs, used algebraic methods to determine Wn(1, q). Our main results in this paper give exact bounds for Wn(p, q), its hypergraph analogue, as well as for a new variant of Bollobás’s Two Families Theorem. In particular, we completely determine Wn(p, q), showing that if 1 ≤ p ≤ q ≤ n then Wn(p, q) = n 2 − (n − p+ 1)2 + (q − p)2. Our proof applies a reduction to a multi-partite version of the Two Families Theorem obtained by Alon. While the reduction is combinatorial, the main idea behind it is algebraic.