×

zbMATH — the first resource for mathematics

Families of finite sets in which no set is covered by the union of \(r\) others. (English) Zbl 0587.05021
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.
Reviewer: Walter Carnielli

MSC:
05B40 Combinatorial aspects of packing and covering
05A99 Enumerative combinatorics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] B. Bollobás,On generalized graphs, Acta Math. Acad. Sci. Hungar.16 (1965), 447–452. · Zbl 0138.19404
[2] B. Bollobás, D. E. Daykin and P. Erdös,On the number of independent edges in a hypergraph, Quart. J. Math. Oxford (2)27 (1976), 25–32. · Zbl 0337.05135
[3] P. Erdös,A problem of independent r-tuples, Ann. Univ. Budapest8 (1965), 93–95. · Zbl 0136.21302
[4] P. Erdös, P. Frankl and Z. Füredi,Families of finite sets in which no set is covered by the union of two others, J. Comb. Theory, Ser. A33 (1982), 158–166. · Zbl 0489.05003
[5] P. Erdös and T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar.10 (1959), 337–356. · Zbl 0090.39401
[6] P. Erdös, C. Ko and R. Rado,An intersection theorem for finite sets, Quart. J. Math. Oxford (2)12 (1961), 313–320. · Zbl 0100.01902
[7] P. Erdös and E. Szemerédi,Combinatorial properties of a system of sets, J. Comb. Theory, Ser. A24 (1978), 308–311. · Zbl 0383.05002
[8] P. Frankl,On Sperner families satisfying an additional condition, J. Comb. Theory Ser. A20 (1976), 1–11. · Zbl 0328.05002
[9] P. Frankl,A general intersection theorem for finite sets, Ann. Discrete Math.8 (1980), 43–49. · Zbl 0468.05016
[10] V. Rödl,On a packing and covering problem, Eur. J. Combinatorics5 (1984).
[11] J. Sperner,Ein Satz über Untermengen einer endlichen Menge, Math. Z.27 (1928), 544–548. · JFM 54.0090.06
[12] F. K. Hwang and V. T. Sós,Non-adaptive hypergeometric group testing, Studia Sci. Math. Hungar., to appear. · Zbl 0639.62076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.