*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.][1] 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][2] 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][2].


**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][2]): 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][3] 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][2].

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

  [1]: https://nature.com/articles/s41586-020-2885-5
  [2]: https://perso.math.u-pem.fr/kloeckner.benoit/papiers/Pooling.pdf
  [3]: https://en.wikipedia.org/wiki/Complete_quadrangle