کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656772 | 1632982 | 2015 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Journal of Combinatorial Theory, Series B - Volume 111, March 2015, Pages 242–248