Tracing a single user

Noga Alon; Vera Asodi

doi:10.1016/j.ejc.2006.05.001

Tracing a single user

Noga Alon
, Vera Asodi

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

Let g (n, r) be the maximum possible cardinality of a family F of subsets of {1, 2, ..., n} so that given a union of at most r members of F, one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that g (n, r) = 2^{Θ (frac(n, r))}, thus solving a problem of Csu{double acute}rös and Ruszinkó.

Original language	English (US)
Pages (from-to)	1227-1234
Number of pages	8
Journal	European Journal of Combinatorics
Volume	27
Issue number	8 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.ejc.2006.05.001
State	Published - Nov 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2006.05.001

Cite this

@article{808abf5aa14d4dc78206e760e79bfe41,

title = "Tracing a single user",

abstract = "Let g (n, r) be the maximum possible cardinality of a family F of subsets of \{1, 2, ..., n\} so that given a union of at most r members of F, one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that g (n, r) = 2Θ (frac(n, r)), thus solving a problem of Csu\{double acute\}r{\"o}s and Ruszink{\'o}.",

author = "Noga Alon and Vera Asodi",

note = "Funding Information: The first author{\textquoteright}s research was supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.",

year = "2006",

month = nov,

doi = "10.1016/j.ejc.2006.05.001",

language = "English (US)",

volume = "27",

pages = "1227--1234",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "8 SPEC. ISS.",

}

TY - JOUR

T1 - Tracing a single user

AU - Alon, Noga

AU - Asodi, Vera

N1 - Funding Information: The first author’s research was supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 2006/11

Y1 - 2006/11

N2 - Let g (n, r) be the maximum possible cardinality of a family F of subsets of {1, 2, ..., n} so that given a union of at most r members of F, one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that g (n, r) = 2Θ (frac(n, r)), thus solving a problem of Csu{double acute}rös and Ruszinkó.

AB - Let g (n, r) be the maximum possible cardinality of a family F of subsets of {1, 2, ..., n} so that given a union of at most r members of F, one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that g (n, r) = 2Θ (frac(n, r)), thus solving a problem of Csu{double acute}rös and Ruszinkó.

UR - https://www.scopus.com/pages/publications/33748563108

UR - https://www.scopus.com/pages/publications/33748563108#tab=citedBy

U2 - 10.1016/j.ejc.2006.05.001

DO - 10.1016/j.ejc.2006.05.001

M3 - Article

AN - SCOPUS:33748563108

SN - 0195-6698

VL - 27

SP - 1227

EP - 1234

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 8 SPEC. ISS.

ER -

Tracing a single user

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this