Skip to main content
The probabilistic method was not implemented correctly, removed it pending further investigation.
Source Link
Benoît Kloeckner
  • 14.4k
  • 1
  • 60
  • 106

An interesting direction, uncovered by @LouisD's answer mentioning [EFF] (Erdős, Paul; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of (r) others, Isr. J. Math. 51, 79-89 (1985). ZBL0587.05021), is to find a family $V$ of $k$-subsets of a $n$-set $E$, such that no two elements in the family intersect in more than $t$ points. Then associating each subset to a taking, and each element of $E$ to a pool, we get a pooling design with detection capacity at least $\lceil \frac k t\rceil-1$ since it needs at least $\lceil \frac k t\rceil$ elements of the family to cover any other elements. Below, I sketch two ways to produce such examples.

1. Geometry and finite fields

One For this, one can use finite fields in a number of way, using for example the fact that two lines of a projective space over $\mathbb{F}_q$ intersect in at most $1$ points (this can be generalized to other dimensions).

Among the pretty effective pooling designs one can get this way, let us mention two that are not equivalent to previously described in the other anwsers.

1.1. Consider $E=\mathbb{F}_3^3$ and $V$ the set of its affine lines. Then we get $v=117$, $e=27$ and $c=2$.

1.2 Consider $E=\mathbb{P}^3\mathbb{F}_3^4$ and $V$ the set of its (projective) lines. Then we have $v=130$, $e=40$ and $c=2$.

Very high compression rates can be achieved with $2$-planes in $4$-dimensional spaces, but the detection capacity stays moderate and this seems only applicable in low prevalence. Low compression rates but high detection capacity are achieved by taking large $q$ and working in dimension $2$.

2Edit. The probabilistic method

To cover the range of moderate, but not low, prevalence (say $5-10\%$) it seems difficult to use the above. Having just read an Erdos paper, wemust try the probabilistic Removed another method. Let us give an example with very rough computations.

Draw randomly and independently $N$ $k$-subsets in a set of cardinal $3k$. Then the probability that any two of these sets intersect in more than one element is $$ \frac{{k \choose 2}{2k \choose k-2}}{{3k \choose k}} \simeq \Big(\frac{16}{27}\Big)^k$$ up to a polynomial factor. The probability that no two of the chosen subsets intersect in more than one point is positive as soon as $\simeq N^2/2$ is less than $\simeq\big(\frac{16}{27}\big)^k$, in particular we can easily take $N = 10k$ say, for $k$ large enough. This gives a pooling design usable at prevalence $\simeq 10\%$ with compression by a factor more than $3$. One only has to find a $k$ compatible with practical considerations, and run a computer until a suitable design is foundwhose computations where way wrong.

An interesting direction, uncovered by @LouisD's answer mentioning [EFF] (Erdős, Paul; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of (r) others, Isr. J. Math. 51, 79-89 (1985). ZBL0587.05021), is to find a family $V$ of $k$-subsets of a $n$-set $E$, such that no two elements in the family intersect in more than $t$ points. Then associating each subset to a taking, and each element of $E$ to a pool, we get a pooling design with detection capacity at least $\lceil \frac k t\rceil-1$ since it needs at least $\lceil \frac k t\rceil$ elements of the family to cover any other elements. Below, I sketch two ways to produce such examples.

1. Geometry and finite fields

One can use finite fields in a number of way, using for example the fact that two lines of a projective space over $\mathbb{F}_q$ intersect in at most $1$ points (this can be generalized to other dimensions).

Among the pretty effective pooling designs one can get this way, let us mention two that are not equivalent to previously described in the other anwsers.

1.1. Consider $E=\mathbb{F}_3^3$ and $V$ the set of its affine lines. Then we get $v=117$, $e=27$ and $c=2$.

1.2 Consider $E=\mathbb{P}^3\mathbb{F}_3^4$ and $V$ the set of its (projective) lines. Then we have $v=130$, $e=40$ and $c=2$.

Very high compression rates can be achieved with $2$-planes in $4$-dimensional spaces, but the detection capacity stays moderate and this seems only applicable in low prevalence. Low compression rates but high detection capacity are achieved by taking large $q$ and working in dimension $2$.

2. The probabilistic method

To cover the range of moderate, but not low, prevalence (say $5-10\%$) it seems difficult to use the above. Having just read an Erdos paper, wemust try the probabilistic method. Let us give an example with very rough computations.

Draw randomly and independently $N$ $k$-subsets in a set of cardinal $3k$. Then the probability that any two of these sets intersect in more than one element is $$ \frac{{k \choose 2}{2k \choose k-2}}{{3k \choose k}} \simeq \Big(\frac{16}{27}\Big)^k$$ up to a polynomial factor. The probability that no two of the chosen subsets intersect in more than one point is positive as soon as $\simeq N^2/2$ is less than $\simeq\big(\frac{16}{27}\big)^k$, in particular we can easily take $N = 10k$ say, for $k$ large enough. This gives a pooling design usable at prevalence $\simeq 10\%$ with compression by a factor more than $3$. One only has to find a $k$ compatible with practical considerations, and run a computer until a suitable design is found.

An interesting direction, uncovered by @LouisD's answer mentioning [EFF] (Erdős, Paul; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of (r) others, Isr. J. Math. 51, 79-89 (1985). ZBL0587.05021), is to find a family $V$ of $k$-subsets of a $n$-set $E$, such that no two elements in the family intersect in more than $t$ points. Then associating each subset to a taking, and each element of $E$ to a pool, we get a pooling design with detection capacity at least $\lceil \frac k t\rceil-1$ since it needs at least $\lceil \frac k t\rceil$ elements of the family to cover any other elements.

For this, one can use finite fields in a number of way, using for example the fact that two lines of a projective space over $\mathbb{F}_q$ intersect in at most $1$ points (this can be generalized to other dimensions).

Among the pretty effective pooling designs one can get this way, let us mention two that are not equivalent to previously described in the other anwsers.

1.1. Consider $E=\mathbb{F}_3^3$ and $V$ the set of its affine lines. Then we get $v=117$, $e=27$ and $c=2$.

1.2 Consider $E=\mathbb{P}^3\mathbb{F}_3^4$ and $V$ the set of its (projective) lines. Then we have $v=130$, $e=40$ and $c=2$.

Very high compression rates can be achieved with $2$-planes in $4$-dimensional spaces, but the detection capacity stays moderate and this seems only applicable in low prevalence. Low compression rates but high detection capacity are achieved by taking large $q$ and working in dimension $2$.

Edit. Removed another method, whose computations where way wrong.

Source Link
Benoît Kloeckner
  • 14.4k
  • 1
  • 60
  • 106

An interesting direction, uncovered by @LouisD's answer mentioning [EFF] (Erdős, Paul; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of (r) others, Isr. J. Math. 51, 79-89 (1985). ZBL0587.05021), is to find a family $V$ of $k$-subsets of a $n$-set $E$, such that no two elements in the family intersect in more than $t$ points. Then associating each subset to a taking, and each element of $E$ to a pool, we get a pooling design with detection capacity at least $\lceil \frac k t\rceil-1$ since it needs at least $\lceil \frac k t\rceil$ elements of the family to cover any other elements. Below, I sketch two ways to produce such examples.

1. Geometry and finite fields

One can use finite fields in a number of way, using for example the fact that two lines of a projective space over $\mathbb{F}_q$ intersect in at most $1$ points (this can be generalized to other dimensions).

Among the pretty effective pooling designs one can get this way, let us mention two that are not equivalent to previously described in the other anwsers.

1.1. Consider $E=\mathbb{F}_3^3$ and $V$ the set of its affine lines. Then we get $v=117$, $e=27$ and $c=2$.

1.2 Consider $E=\mathbb{P}^3\mathbb{F}_3^4$ and $V$ the set of its (projective) lines. Then we have $v=130$, $e=40$ and $c=2$.

Very high compression rates can be achieved with $2$-planes in $4$-dimensional spaces, but the detection capacity stays moderate and this seems only applicable in low prevalence. Low compression rates but high detection capacity are achieved by taking large $q$ and working in dimension $2$.

2. The probabilistic method

To cover the range of moderate, but not low, prevalence (say $5-10\%$) it seems difficult to use the above. Having just read an Erdos paper, wemust try the probabilistic method. Let us give an example with very rough computations.

Draw randomly and independently $N$ $k$-subsets in a set of cardinal $3k$. Then the probability that any two of these sets intersect in more than one element is $$ \frac{{k \choose 2}{2k \choose k-2}}{{3k \choose k}} \simeq \Big(\frac{16}{27}\Big)^k$$ up to a polynomial factor. The probability that no two of the chosen subsets intersect in more than one point is positive as soon as $\simeq N^2/2$ is less than $\simeq\big(\frac{16}{27}\big)^k$, in particular we can easily take $N = 10k$ say, for $k$ large enough. This gives a pooling design usable at prevalence $\simeq 10\%$ with compression by a factor more than $3$. One only has to find a $k$ compatible with practical considerations, and run a computer until a suitable design is found.