##
**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 F_{0}\subset /F_{1}\cup F_{2}\cup...\cup F_{r}, for every distinct F_{0},F_{1},...,F_{r}. Denoting by f_{r}(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 f_{r}(n,k) \leq \binom{n}{t}/\binom{k-1}{t-1} for every n,k and r (where t = [k/r]) and that f_{r}(n,r(t-1)+1+d) \leq \binom{n-d}{t}/\binom{k-d}{t} for d = 0,1 or d \leq r/2t^{2}. 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 f_{r}(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