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ó.

We consider the problem of learning a labeled graph from a given family of graphs on n vertices in a model where the only allowed operation is to query whether a set of vertices induces an edge. Questions of this type are motivated by problems in molecular biology. In the deterministic nonadaptive setting, we prove nearly matching upper and lower bounds for the minimum possible number of queries required when the family is the family of all stars of a given size or all cliques of a given size. We further describe some bounds that apply to general graphs.