I realize this is long, but hopefully I think it may be worth the reading for people interested in combinatorics and it might prove important to Covid-19 testing. Slightly reduced in edit.

0. Introduction

The starting point of this question is this important article by Mutesa et al. where a hypercube $\{0,1,2\}^n$ is used for pooling takings for Covid-19 testing. This pooling design is only usable at low prevalence, and might be improvable even at low prevalence.

I have written a draft sketching some possible research directions, and I would like to share here the main point and ask here what seem to me to be the main questions. It might be better to set up a Polymath project, but I don't feel I have the skills (I am not a combinatorician myself) nor the proper network to make it work.

1. Definitions

Assume we are given takings from many patients to be analyzed for presence of a virus by RT-PCR; up to the usual limits in sensitivity and specificity, a pool where several takings are mixed will be positive if and only if at least one of the patients has the disease. We will model the different mixes by a hypergraph, i.e. a pair $(V,E)$ where $V$ is a set (whose elements are called vertices and represent patients) and $E$ is a set of non-empty subsets of $V$ (whose elements are called edges and represent pools).

Definition Given a vertex $x\in V$, let $x^*$ be the set of edges containing $x$. Given a subset $X\subset V$ of vertices, let $X^*=\{e\in E \mid \exists x\in X, x\in e\}$ be the set of all edges incident to some element of $X$. Let us define a pooling design as a hypergraph $(V,E)$ satisfying the following property: $$\forall x\in V, \forall X\subset V, \quad x^* = X^* \implies X=\{x\}$$

This condition ensures that, whenever there is at most one positive taking, its uniqueness is guaranteed by the tests and it can be identified.

Given a pooling design $(V,E)$, there are several numbers of importance to analyze its practical interest in pooled testing. Among them we mention: its order $v=\lvert V\rvert$, its size $e=\lvert E\rvert$, its compression rate $$r=\frac{e}{v}$$ (the smaller, the better), and its detection capacity, i.e. the maximal number of positive taking that can be guaranteed and identified. Formally, letting $\mathcal{P}_{\le n}(V)$ be the set of subsets of $V$ with at most $n$ elements, we set $$c = \max \big\{n\colon \forall X,Y\in \mathcal{P}_{\le n}(V), X^*=Y^*\implies X=Y \big\}.$$ The definition of a pooling design ensures $c\ge 1$, but larger is better.

2. A compression rate is limited by relative detection capability

Proposition. Let $(V,E)$ be a pooling design of order $v$, size $e$ and detection capacity $c$. Then the compression rate satisfies $$r \ge H\big(\frac{c}{v}\big) - o_{v\to\infty}(1) $$

In particular, since the prevalence at which the pooling design can be used is mostly driven by $c/v$, we have a quantitative estimate of how much a large prevalence prevents a good compression rate. The proof is straightfoward, and sketched in the draft.

3. Examples

Example 1. The individual testing consist in taking $V$ the set of all $N$ takings, and $E=\big\{\{x\} \colon x\in V\big\}$: each edge is a single vertex. We call this the trivial pooling design of order $v$; it has \begin{align*} v &= e = N & r &= 1 & c &= N \end{align*}

Example 2. The hypercube design of (Mutesa et al. 2020) with dimension $D\ge2$ consist in taking $V=\{1,2,3\}^D$ and $E$ the set of coordinate slices, i.e. $$E=\bigcup_{k=1}^D \big\{\{1,2,3\}^{k-1}\times \{i\}\times\{1,2,3\}^{D-k} \colon i\in\{1,2,3\}\big\}.$$ It has \begin{align*} v &= 3^D & e &= 3D & r &= \frac{D}{3^{D-1}} & c &= 1 \end{align*}

Comparing $H(c/v)$ and the actual compression rate for the hypercube design with various values of $D$ show some limited room for improvement (see the draft): the hypercube is off by only a factor less than $2$; these pooling designs are thus not too far from optimal in their prevalence regime.

Example 3. The complete quadrilateral can be described with $V=\{1,2,3,4,5,6\}$ and $E=\big\{ \{1,2,3\}, \{3,4,5\}, \{5,6,2\}, \{1,4,6\} \big\}$. It has \begin{align*} v &= 6 & e &= 4 & r &= \frac23 & c &= 1 \end{align*} For comparison, we note that $H(c/v) \simeq 0.65$, very close to the compression rate: this pooling design is close to optimal in its prevalence regime.

Other examples from incidence geometry are given in the draft.

Example 4. Let $p$ be a prime number (or a primitive number) and $\mathbb{F}_p$ be the Field with $p$ elements. Choose a dimension $D\ge 2$ and a parameter $k\ge D$. We set $V=\mathbb{F}_p^D$ (for $p=3$, we thus have the same vertex set than in the hypercube design). Let $(\phi_1,\dots,\phi_k)$ be linear forms such that any $D$ of them are linearly independent. Without loss of generality, we can assume $(\phi_1,\dots,\phi_D)$ is the canonical dual basis (i.e. $\phi_i(x_1,\dots,x_D) = x_i$). Last, we let $E$ be the set of all levels of all the $\phi_i$: $$ E = \big\{\phi_i^{-1}(y) \colon i\in\{1,\dots, k\}, y\in\mathbb{F}_p \big\}.$$ Let us call the pooling design $(V,E)$ the generalized hybercube design of parameters $(p,D,k)$. It has \begin{align*} v &= p^D & e &= kp & r &= \frac{k}{p^{D-1}} \end{align*} and the remaining question is how large can be $c$. I think that for $k=D+1$, $c\ge2$.

For example, with $p=3$, $D=5$ and $k=6$ this gives $H(c/v)\ge 0.068$ and $r\simeq 0.074$, a relative improvement from the hypercube design of the same dimension. With $p=2$, $D=5$ and $k=6$, we get a moderate-order pooling design ($v=32$) with $H(c/v)\ge 0.33$ and nearly optimal $r= 0.375$.

4. Questions

General Question Which values of $v,r,c$ are realized by a pooling design?

Question 1. Determine $c$ for the generalized hypercube design, in particular confirm that $c\ge 2$ when $k>D$ (it might be that $c$ depends on the specific linear form chosen, although I would bet a low stake that it does not). Given $v_0$, what choice of $p,D,k$ such that $v\simeq v_0$ minimizes $\frac{r}{H(c/v)}$? Given a prevalence, what is the best value of $r$ that can be achieved with a generalized hypercube for which detection capacity is exceeded with probability less than $5\%$?

Question 2. Does there exist pooling designs with $v\gg 1$, $c/v \simeq 1/6$ and compression rate $\simeq2/3$?

Question 3. For small values of $v$, give all pooling designs that are optimal in the sense that no other pooling design with the same order has both better compression rate and better detection capability.