Families of finite sets in which no set is covered by the union of \(r\) others (Q1072559): Difference between revisions

If \(\mathcal F\) is a collection of \(k\)-subsets of a set \(X\), \(X=\{1,2,\dots,n\}\), \(\mathcal F\) is said to be \(r\)-cover free if \(F_0\subset F_1\cup F_2\cup\cdots\cup F_r\), for every distinct \(F_0,F_1,\dots,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}\bigg/\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}\bigg/\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.