Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656772 | Journal of Combinatorial Theory, Series B | 2015 | 7 Pages |
Let Kp1,…,pdd denote the complete d-uniform d -partite hypergraph with partition classes of sizes p1,…,pdp1,…,pd. A hypergraph G⊆Kn,…,nd is said to be weakly Kp1,…,pdd-saturated if one can add the edges of Kn,…,nd∖G in some order so that at each step a new copy of Kp1,…,pdd is created. Let Wn(p1,…,pd)Wn(p1,…,pd) denote the minimum number of edges in such a hypergraph. The problem of bounding Wn(p1,…,pd)Wn(p1,…,pd) was introduced by Balogh, Bollobás, Morris and Riordan who determined it when each pipi is either 1 or some fixed p . In this note we fully determine Wn(p1,…,pd)Wn(p1,…,pd). 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.