×

zbMATH — the first resource for mathematics

Tracing a single user. (English) Zbl 1105.05068
Denote \(g(n,r)\) the maximum possible cardinality of a family of subsets of an \(n\)-element underlying set so that given a union of at most \(r\) members, one can identify at least one of the members. This has a close connection with the so-called group testing problem applied to design DNA chips in molecular biology. The paper shows that \(g(n,r)=2^{\Theta({n \over r})}.\) The main contribution of the paper is a new lower bound for \(g(n,r)\).

MSC:
05D05 Extremal set theory
92D20 Protein sequences, DNA sequences
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alon, N.; Babai, L.; Itai, A., A fast and simple randomized parallel algorithm for the maximal independent set problem, J. algorithms, 7, 567-583, (1986) · Zbl 0631.68063
[2] N. Alon, D. Moshkovitz, M. Safra, Algorithmic construction of sets for \(k\)-restrictions, ACM Trans. Algorithms (in press) · Zbl 1321.68445
[3] Alon, N.; Beigel, R.; Kasif, S.; Rudich, S.; Sudakov, B., Learning a hidden matching, (), SIAM J. computing, 33, 487-501, (2004), Also: · Zbl 1055.05142
[4] R. Beigel, N. Alon, M.S. Apaydin, L. Fortnow, S. Kasif, An optimal procedure for gap closing in whole genome shotgun sequencing, in: Proc. 2001 RECOMB, ACM Press, pp. 22-30
[5] Balding, D.J.; Bruno, W.J.; Knill, E.; Torney, D.C., A comparative survey of non-adaptive pooling designs, genetic mapping and DNA sequencing, (), 133-154 · Zbl 0860.62083
[6] Colbourn, C.C.; Ling, A.C.H.; Tompa, M., Construction of optimal quality control for oligo arrays, Bioinformatics, 18, 4, 529-535, (2002)
[7] Csűrös, M.; Ruszinkó, M., Single-user tracing and disjointly superimposed codes, IEEE trans. inform. theory, 51, 4, 1606-1611, (2005) · Zbl 1284.94026
[8] Coppersmith, D.; Shearer, J.B., New bounds for union-free families of sets, Electron. J. combin., 5, 1, #R39, (1998)
[9] Dyachkov, A.G.; Rykov, V.V., Bounds on the length of disjunctive codes, Probl. pereda. inf., 18, 3, 158-166, (1982) · Zbl 0524.94015
[10] 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, 79-89, (1985) · Zbl 0587.05021
[11] Füredi, Z., A note on r-cover-free families, J. combin. theory ser. A, 73, 1, 172-173, (1996) · Zbl 0843.05100
[12] Hwang, F.K.; Sós, V.T., Non-adaptive hypergeometric group testing, Studia sci. math. hungar., 22, 257-263, (1987) · Zbl 0639.62076
[13] Kautz, W.H.; Singleton, R.C., Nonrandom binary superimposed codes, IEEE trans. inform. theory, 10, 363-377, (1964) · Zbl 0133.12402
[14] Ruszinkó, M., On the upper bound of the size of the r-cover-free families, J. combin. theory ser. A, 66, 2, 302-310, (1994) · Zbl 0798.05071
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.