×

zbMATH — the first resource for mathematics

On the upper bound of the size of the \(r\)-cover-free families. (English) Zbl 0798.05071
Let \(T(r,n)\) denote the maximum number of subsets of an \(n\)-set such that no subset is covered by the union of any other \(r\) subsets (such a system is called \(r\)-cover-free). It is shown that for \(n\) sufficiently large \[ {\log_ 2 T(r,n)\over n}\leq 8 {\log_ 2 r\over r^ 2}. \] This comes from a better understanding and proof of a result of A. G. Dyachkov and V. V. Rykov. The central element of this proof is a new set compression algorithm.

MSC:
05D05 Extremal set theory
94B25 Combinatorial codes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Nguyen, Q.A; Zeisel, T, Bounds on constant weight binary superimposed codes, Probab. control information theory, 17, 223-230, (1988) · Zbl 0652.94021
[2] Alon, N, Explicit contractions of exponential sized families of k-independent sets, Discrete math., 58, 191-193, (1986) · Zbl 0588.05003
[3] Baranyai, Zs, On the factorization of the complete uniform hypergraph, () · Zbl 0306.05137
[4] Dyachkov, A.G; Rykov, V.V, Bounds on the length of disjunctive codes, Problemy peredachi informatsii, 18, No. 3, 7-13, (1982) · Zbl 0507.94013
[5] Dyachkov, A.G; Rykov, V.V, A survey of superimposed codes theory, Probab. control information theory, 12, No. 4, 1-13, (1983)
[6] Erdős, P; Frankl, P; Fűredi, Z, Families of finite sets in which no set is covered by the union of two others, J. combin. theory, ser. A, 33, No. 2, 158-166, (1982) · Zbl 0489.05003
[7] Erdős, P; Frankl, P; Füredi, Z, Families of finite sets in which no set is covered by the union of r others, Israel J. math., 51, No. 1/2, 79-89, (1985) · Zbl 0587.05021
[8] Frankl, P, On sperner families satisfying an additional condition, J. combin. theory, ser. A, 20, No. 1, 1-11, (1976) · Zbl 0328.05002
[9] Frankl, P; Füredi, Z, Colored packing of sets, Ann. discrete math., 34, 165-178, (1987) · Zbl 0675.05020
[10] Frankl, P; Rődl, V, Near perfect coverings in graphs and hypergraphs, Europ. J. combinatorics, 6, 317-326, (1985) · Zbl 0624.05055
[11] Gallager, R.G, Information theory and reliable communication, () · Zbl 0333.94009
[12] Hwang, F.K, A method for detecting all defective members in a population by group testing, J. amer. statist. assoc., 67, No. 339, 605-608, (1972) · Zbl 0247.62010
[13] Hwang, F.K; Sós, V.T, Non adaptive hypergeometric group testing, Studia sci. math. hungarica, 22, 257-263, (1987) · Zbl 0639.62076
[14] Johnson, S.M, On the upper bounds for unrestricted binary error-correcting codes, IEEE trans. inform. theory, 17, No. 4, 466-478, (1971) · Zbl 0231.94008
[15] Johnson, S.M, Improved asymptotic bounds for error-correcting codes, IEEE trans. inform. theory, 9, No. 4, 198-205, (1963) · Zbl 0282.94010
[16] Johnson, S.M, A new upper bound for error-correcting codes, IRE trans. inform. theory, 8, 203-207, (1962) · Zbl 0102.34602
[17] Kautz, W.H; Singleton, R.C, Nonrandom binary superimposed codes, IEEE trans. inform. theory, 10, 363-377, (Oct. 1964)
[18] Rödl, V, On a packing and covering problem, Europ. J. combin., 5, 69-78, (1985) · Zbl 0565.05016
[19] Sós, V.T, An additive problem in different structures, (), 486-510 · Zbl 0760.05088
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.