Skip to main content
1 of 2
Benoît Kloeckner
  • 14.4k
  • 1
  • 60
  • 106

Let me get started with a small take at question 3. First, for $v\in\{1,2,3\}$ it is clear that no pooling design can have compression rate $r<1$ (so trivial is optimal). For example for $v=3$, we need to distinguish at least $5$ situations (no positives, at least $2$ positives, and $3$ possible single positives), so $2$ bits of information cannot be enough and we must have $e\ge 3$.

Thus $v=4$ is the first case where the trivial bound does not preclude a pooling design of interest (we need to distinguish $6$ situations, leading to the bound $e\ge3$). However:

Proposition. There are no pooling design with $v=4$ and $r<1$.

Proof. Assume $(V,E)$ is a pooling design with $V=\{1,2,3,4\}$ and $e=3$. If an element of $E$ is a singleton, then removing it from $E$ and its element from $V$ would give a pooling design with $v=3$ and $e=2$, which is impossible. If two elements $p,q$ of $E$ are contained one in the other, $p\subset q$, then replacing $q$ with $q\setminus p$ gives a pooling design (more information is carried by the results of $(p,q\setminus p)$ than by the results of $(p,q)$).

We can thus assume that no element of $E$ is a singleton, and no element of $E$ contains another (these are general arguments than can be used more widely).

In particular, all elements of $E$ have $2$ or $3$ elements.

No vertex can belong to all edges, since otherwise the positivity of this vertex would entail positivity of all edges, an event that cannot be distinguished from all vertices being positives.

No vertex $a$ can be contained in only one edge, otherwise the positivity of another vertex $b$ of this edge could not be distinguished from the positivity of $a$ and $b$.

It follows that all vertices must have degree exactly $2$. The total degree is thus $8$, and we must have two elements of $E$ of cardinal $3$ and the last one of cardinal $2$. But then the two largest edges must have two elements in common, which thus have the same link, a contradiction.

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