Exact Bounds for Some Hypergraph Saturation Problems

Original · EN

Let Wₙ(p,q) denote the minimum number of edges in an n x 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 Kₚ,q is created. The problem of bounding Wₙ(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 Wₙ(1,q). Our main results in this paper give exact bounds for Wₙ(p,q), its hypergraph analogue, as well as for a new variant of Bollobás's Two Families theorem. In particular, we completely determine Wₙ(p,q), showing that if 1 <= p <= q <= n then Wₙ(p,q) = n² - (n-p+1)² + (q-p)². 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.