Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 587.05021
Autor: Erdös, Paul; Frankl, P.; Füredi, Z.
Title: Families of finite sets in which no set is covered by the union of r others. (In English)
Source: Isr. J. Math. 51, 79-89 (1985).
Review: If F is a collection of k-subsets of a set X, X = {1,2,...,n}, F is said to be r-cover free if F0\subset /F1\cup F2\cup...\cup Fr, for every distinct F0,F1,...,Fr. Denoting by fr(n,k) the maximum number of k subsets of X which satisfy the above condition, it is proved that \binom{n}{t}/\binom{k}{t}2 \leq fr(n,k) \leq \binom{n}{t}/\binom{k-1}{t-1} for every n,k and r (where t = [k/r]) and that fr(n,r(t-1)+1+d) \leq \binom{n-d}{t}/\binom{k-d}{t} for d = 0,1 or d \leq r/2t2. Equality holds iff there exists a Steiner system S(t,r(t-1)+1,n-d). Particular cases of r-cover free collections (which provide lower bounds for fr(n,tr)) are the families introduced as near t-packing: a collection of tr-subsets of X (t,r \geq 2) is a near t-packing if |F\cap F'| \leq t, and |F\cap F'| = t implies max{i: i in F}\not in F' (for example, the collection {{1,2,3,5},{1,2,4,6},{ 1,3,4,7},{2,3,4,8}} is a near 2-packing in \binom{8}{4}. This is a generalization, in certain sense, of the concept of BIBD. This work is a continuation of a previous paper by the same authors, where they studied the problem of 2-cover free families of sets.
Reviewer: W.Carnielli
Classif.: * 05B40 Packing and covering (combinatorics)
05A99 Classical combinatorial problems
Keywords: coverings; generalization of BIBD; collection of k-subsets; r-cover free
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag