Tracing Many Users With Almost No Rate Penalty

Abstract

For integers $n, r geq 2$ and $1 leq k leq r$, a family ${cal F}$ of subsets of $[n] = {1,ldots,n}$ is called $k$ -out-of-$r$ multiple-user tracing if, given the union of any $ell leq r$ sets from the family, one can identify at least $min(k,ell)$ of them. This is a generalization of superimposed families $(k = r)$ and of single-user tracing families $(k = 1)$. The study of such families is motivated by problems in molecular biology and communication. In this correspondence, we study the maximum possible cardinality of such families, denoted by $h(n,r,k)$ , and show that there exist absolute constants $c_1, c_2, c_3, c_4 > 0$ such that $$minleft({c_1over r}, {c_3over k^2}right) leq {log h(n,r,k)over n} leq minleft({c_2over r}, {c_4 log k over k^2}right).$$ In particular, for all $k leq sqrt{r}, ,{log h(n,r,k)over n} =Theta(1/r)$. This improves an estimate of Laczay and Ruszinkó.