RT-PCR 테스트를위한 효율적인 풀링 설계는 무엇입니까?
나는 이것이 길다는 것을 알고 있지만, 조합론에 관심이있는 사람들이 읽을만한 가치가 있다고 생각하며 Covid-19 테스트에 중요 할 수 있습니다. 편집에서 약간 감소했습니다 .
이 질문의 시작점은 Mutesa et al. 하이퍼 큐브$\{0,1,2\}^n$Covid-19 테스트를위한 풀링 테이크에 사용됩니다. 이 풀링 디자인은 낮은 유병률에서만 사용할 수 있으며, 주요 질문은 유병률 범위에서 개선 할 수 있는지 여부와 더 높은 유병률에서 사용할 수있는 좋은 풀링 디자인을 찾을 수 있는지 여부입니다.
나는 몇 가지 가능한 연구 방향을 스케치 한 초안 을 작성했으며 여기에서 주요 요점을 공유하고 여기에서 주요 질문으로 보이는 것이 무엇인지 묻고 싶습니다. Polymath 프로젝트를 설정하는 것이 더 나을 수 있지만 기술 (저는 조합 학자가 아닙니다)도 제대로 작동 할 수있는 적절한 네트워크가 없다고 생각합니다.
하이퍼 그래프 , 즉 쌍으로 Covid-19에 대한 풀링 된 PCR 테스트를 모델링합니다.$(V,E)$ 어디 $V$ 집합 (그 요소를 정점이라고하며 환자를 나타냄)이며 $E$ 비어 있지 않은 부분 집합의 집합입니다. $V$(그 요소를 가장자리라고하며 풀을 나타냄). 기억하세요$v=\lvert V\rvert$하이퍼 그래프 의 순서 이고$e=\lvert E\rvert$ 그것의 치수; $v$ 일괄 적으로 분석 된 복용 횟수 $e$ 병렬로 실행할 테스트 수입니다.
정점이 주어진 정의$x\in V$, 허락하다 $x^*$ 포함하는 모서리 세트 $x$. 하위 집합이 주어짐$X\subset V$ 정점의 $X^*=\{e\in E \mid \exists x\in X, x\in e\}$ 어떤 요소에 입사하는 모든 모서리의 집합 $X$. 풀링 설계 를 하이퍼 그래프로 정의하겠습니다.$(V,E)$ 다음 속성을 충족합니다. $$\forall x\in V, \forall X\subset V, \quad x^* = X^* \implies X=\{x\}$$
이 조건은 최대 한 번의 긍정적 인 복용이있을 때마다 검사에 의해 고유성이 보장되고 식별 될 수 있도록합니다.
풀링 설계가 주어지면 $(V,E)$, 우리는 압축률 을 정의합니다. $$r=\frac{e}{v}$$(작을수록 더 좋음), 감지 능력 , 즉 보장되고 식별 될 수있는 최대 양성 복용 횟수. 공식적으로$\mathcal{P}_{\le n}(V)$ 하위 집합의 집합 $V$ 기껏해야 $n$ 요소, 우리는 설정 $$c = \max \big\{n\colon \forall X,Y\in \mathcal{P}_{\le n}(V), X^*=Y^*\implies X=Y \big\}.$$ 풀링 설계의 정의는 다음을 보장합니다. $c\ge 1$,하지만 클수록 좋습니다.
제안. 허락하다$(V,E)$ 질서의 통합 설계 $v$, 크기 $e$ 및 감지 용량 $c$. 그런 다음 압축률은$$r \ge H\big(\frac{c}{v}\big) - o_{v\to\infty}(1) $$
증명은 간단하며 초안에 스케치되어 있습니다.
예 1. 개별 테스트는$V$ 모두의 집합 $N$ 복용 및 $E=\big\{\{x\} \colon x\in V\big\}$: 각 모서리는 단일 정점입니다. 우리는 이것을 주문 의 사소한 풀링 디자인 이라고 부릅니다.$v$; 그것은 가지고있다\begin{align*} v &= e = N & r &= 1 & c &= N \end{align*}
예 2. 차원이있는 (Mutesa et al. 2020)의 하이퍼 큐브 디자인$D\ge2$ 복용으로 구성 $V=\{1,2,3\}^D$ 과 $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\}.$$ 그것은 가지고있다 \begin{align*} v &= 3^D & e &= 3D & r &= \frac{D}{3^{D-1}} & c &= 1 \end{align*}
비교 $H(c/v)$ 다양한 값을 가진 하이퍼 큐브 디자인의 실제 압축률 $D$개선의 여지가 제한되어 있음 ( 초안 참조 ) : 하이퍼 큐브가$2$; 따라서 이러한 풀링 설계는 보급 체제에서 최적과 그리 멀지 않습니다.
예 3 완전한 사각형을 설명 할 수있다$V=\{1,2,3,4,5,6\}$ 과 $E=\big\{ \{1,2,3\}, \{3,4,5\}, \{5,6,2\}, \{1,4,6\} \big\}$. 그것은 가지고있다\begin{align*} v &= 6 & e &= 4 & r &= \frac23 & c &= 1 \end{align*} 비교를 위해 우리는 $H(c/v) \simeq 0.65$, 압축률에 매우 가깝습니다.이 풀링 설계는 유병률 영역에서 최적에 가깝습니다.
입사 지오메트리의 다른 예가 드래프트에 제공 됩니다.
예 4. Let$p$ 소수 (또는 원시 숫자)이고 $\mathbb{F}_p$ 함께 필드가 $p$집단. 치수 선택$D\ge 2$ 및 매개 변수 $k\ge D$. 우리는 설정$V=\mathbb{F}_p^D$ (에 대한 $p=3$, 따라서 우리는 하이퍼 큐브 디자인에서와 동일한 정점 세트를 갖습니다). 허락하다$(\phi_1,\dots,\phi_k)$ 다음과 같은 선형 형태 $D$그들 중 선형 적으로 독립적입니다. 일반성을 잃지 않고 가정 할 수 있습니다.$(\phi_1,\dots,\phi_D)$ 표준 이중 기준입니다 (예 : $\phi_i(x_1,\dots,x_D) = x_i$). 마지막으로$E$ 모든 수준의 집합이 $\phi_i$: $$ E = \big\{\phi_i^{-1}(y) \colon i\in\{1,\dots, k\}, y\in\mathbb{F}_p \big\}.$$ 풀링 디자인이라고 부르 자 $(V,E)$매개 변수 의 일반화 된 하이버 큐브 설계$(p,D,k)$. 그것은 가지고있다\begin{align*} v &= p^D & e &= kp & r &= \frac{k}{p^{D-1}} \end{align*} 나머지 질문은 얼마나 클 수 있는지 $c$.
일반 질문 어느 값$v,r,c$ 풀링 설계로 실현됩니까?
질문 1. 결정$c$ 일반화 된 하이퍼 큐브 디자인의 경우 ( $c$선택한 특정 선형 형식에 따라 다르지만 그렇지 않은 경우 낮은 지분을 걸겠습니다.) 주어진$v_0$, 어떤 선택 $p,D,k$ 그런 $v\simeq v_0$ 최소화 $\frac{r}{H(c/v)}$? 유병률을 감안할 때 가장 좋은 가치는 무엇입니까?$r$ 일반화 하이퍼 큐브로 달성 할 수있는 $5\%$?
질문 2. 풀링 디자인이 있습니까?$v\gg 1$, $c/v \simeq 1/6$ 및 압축률 $\simeq2/3$?
질문 3. 작은 값의 경우$v$, 동일한 순서를 가진 다른 풀링 디자인이 더 나은 압축률과 더 나은 감지 기능을 모두 가지고 있지 않다는 점에서 최적의 모든 풀링 디자인을 제공하십시오.
질문 4. 정의를 일반화하고 탐지 용량을 대체하면 위의 질문 중 어느 것이 더 간단 해 집니까?$c$ 세트로 $\mathcal{D}$ 의 $X\subset V$ 이러한 $X^*=Y^* \implies X=Y$ 모든 $Y\subset V$? (그런 다음 유행에 풀링의 성능$p$ 긍정적 인 결과가 나올 확률이 $\mathcal{D}$, 인수가 Bernoulli 매개 변수 법칙을 사용하는 IID 랜덤 변수라고 가정합니다. $p$).
답변
질문 3 에서이를 증명하여 간단히 시작하겠습니다.$v\le 6$, 완전한 사변형이 최적입니다.
첫째, $v\in\{1,2,3\}$ 어떤 풀링 설계도 압축률을 가질 수 없음이 분명합니다. $r<1$(너무 사소한 것이 최적입니다). 예를 들어$v=3$, 우리는 적어도 구별해야 $5$ 상황 (긍정적 없음, 적어도 $2$ 긍정적이고 $3$ 가능한 단일 긍정), 그래서 $2$ 약간의 정보로는 충분하지 않으며 $e\ge 3$.
그러므로 $v=4$ 사소한 경계가 관심있는 풀링 설계를 배제하지 않는 첫 번째 경우입니다 (우리는 $6$ 상황, 경계로 이어지는 $e\ge3$). 하나:
제안. 풀링 디자인이 없습니다.$v=4$ 과 $r<1$.
증명. 취하다$(V,E)$ 풀링 디자인입니다. $V=\{1,2,3,4\}$ 과 $e=3$. 요소가$E$ 싱글 톤이고 다음에서 제거합니다. $E$ 및 그 요소 $V$ 풀링 디자인을 제공합니다 $v=3$ 과 $e=2$, 불가능합니다. 두 요소가$p,q$ 의 $E$ 다른 하나에 포함되어 있습니다. $p\subset q$, 다음 교체 $q$ 와 $q\setminus p$ 풀링 설계를 제공합니다 (더 많은 정보는 $(p,q\setminus p)$ 의 결과보다 $(p,q)$).
따라서 우리는 $E$ 싱글 톤이고 $E$다른 것을 포함합니다 (이들은 더 널리 사용될 수있는 일반적인 주장입니다).
특히 $E$ 있다 $2$ 또는 $3$ 집단.
정점은 모든 가장자리에 속할 수 없습니다. 그렇지 않으면이 정점의 긍정 성이 모든 가장자리의 긍정 성을 수반하므로 모든 정점이 긍정 인 것과 구별 할 수없는 이벤트입니다.
정점 없음 $a$하나의 가장자리에만 포함될 수 있습니다 . 그렇지 않으면 다른 정점의 긍정 성$b$ 이 가장자리의 긍정과 구별 할 수 없었습니다 $a$ 과 $b$.
모든 정점은 정확히 차수를 가져야합니다. $2$. 따라서 총 학위는$8$, 두 가지 요소가 있어야합니다. $E$ 추기경 $3$ 그리고 마지막 추기경 $2$. 그러나 두 개의 가장 큰 모서리는 공통된 두 요소를 가져야합니다. 따라서 동일한 링크, 즉 모순이 있습니다.$\square$
동일한 주장이 다음과 같이 이어집니다.
제안. 풀링 디자인$v=5$ 있어야한다 $e\ge 4$.
참고 $(v,e) = (5,4)$ 완전한 사변형에서 정점을 제거하여 실현할 수 있습니다.
증명. 그것을 가정$(V,E)$ 풀링 디자인입니다. $v=5$ 과 $e=3$. 그런 다음 가장자리에는 추기경이 있습니다.$2,3$ 또는 $4$ 그리고 그 정점은 모두 차수를 가지고 있습니다. $2$. 총 학위는$10$두 가지 방법으로 달성 할 수 있습니다.
첫째, 분해 $10=4+4+2$, 즉 두 모서리가 $4$각 요소. 하지만이 모서리는 두 가지 요소를 공통으로 가지고 있는데, 이는 학위가 있기 때문에 구별 할 수 없습니다.$2$.
둘째, 분해 $10=4+3+3$. 그런 다음$V=\{1,2,3,4,5\}$ 과 $E=\{p,q,r\}$ 와 $p=\{1,2,3,4\}$, 우리는 $5^* = \{q,r\}$. 각각$q$ 과 $r$ 있다 $3$ 다음을 포함한 요소 $5$. 따라서 대칭까지$q=\{1,2,5\}$ 과 $r=\{3,4,5\}$. 그때$1^*=2^*$ 과 $3^*=4^*$, 불가능합니다. $\square$
추론. 완전한 사변형이 주문에 최적입니다.$6$. 주문$v< 6$, 압축률이있는 유일한 다른 풀링 설계 $r<1$ 완전한 사변형에서 하나의 정점을 제거하여 얻을 수 있습니다.
이것은 완전한 대답은 아니지만 코멘트를하기에는 너무 깁니다. 질문 3이나 하이퍼 큐브 디자인을 개선 할 수 있는지에 대한 일반적인 질문에 가장 가깝다고 생각합니다.
하이퍼 그래프가 주어진 정의$G=(\{v_1, \dots, v_n\}, E)$는 이중 의$G$ 하이퍼 그래프 $H$ 와 $V(H)=E(G)$ 과 $E(H)=\{\{e\in E(G): v_i\in e\}: i\in [k]\}$ (즉, 각 모서리 $H$ 최대 모서리 모음입니다. $G$ 단일 정점으로 발생).
허락하다 $H_{n,k}$ 이중이다 $K_n^{k}$, 완전한 $k$-일반 하이퍼 그래프 $n$정점. 이중의$H_{n,k}$ 동형이다 $K_n^k$.
(이 하이퍼 그래프는 이전에 연구 된 적이있는 것 같지만 그에 대한 참조를 찾을 수 없었습니다. 가능한 단서는 다음과 같습니다. $H_{4,2}$완전한 사변형 이라고 부르는 것 입니다.)
주장 1. $H_{n,k}$ 이다 $\binom{n-1}{k-1}$-제복 $k$-일반 하이퍼 그래프 $\binom{n}{k}$ 정점 및 $n$ 가장자리.
증명. 에$K_n^k$, 모든 정점은 $\binom{n-1}{k-1}$ 가장자리, 모든 가장자리에는 순서가 있습니다. $k$, 있습니다 $\binom{n}{k}$ 가장자리 및 $n$ 정점.$\square$
주장 2. $H_{n,k}$ 풀링 디자인입니다.
증명. 모든 정점$H_{n,k}$ 에 사건이다 $k$ 가장자리, 그래서 $|x^*|=k$. 만약$X$ 다음과 같은 정점 세트입니다. $|X|>1$ (하나 이상의 모서리 집합에 해당합니다. $K_n^k$, 이상에 걸쳐 있음 $k$ 정점 $K_n^k$) 다음 $|X^*|>k$. 그래서$x^*\neq X^*$ 만약 $|X|>1$.$\square$
압축률 $H_{n,k}$ 이다 $\frac{n}{\binom{n}{k}}$ 최소화 될 때 $k=\lfloor{n/2}\rfloor$. 또한 정점 수에 대한 균일 성의 비율은$\binom{n-1}{k-1}/\binom{n}{k}=k/n$. 따라서 압축률을 최소화 할 때 트레이드 오프가 있습니다.$k$.
더 많은 예 : $H_{5,2}$ 10 개의 정점과 5 개의 가장자리로 구성된 4- 균일로 압축 비율은 $1/2$. $H_{6,3}$ 20 개의 정점과 6 개의 가장자리를 가진 10- 균일 한 압축 비율을 제공합니다. $3/10$. $H_{7,3}$ 35 개의 꼭지점과 7 개의 가장자리로 15- 균일하여 압축 비율을 제공합니다. $1/5$. 하이퍼 큐브 디자인은$D=3$ 27 개의 꼭지점과 9 개의 가장자리가있는 9-regular이므로 압축 비율이 1/3이므로 $H_{6,3}$ 과 $H_{7,3}$ 이 경우 유리하게 비교하십시오.
업데이트 1 . (새 답변을 작성하는 것보다 이전 답변을 업데이트하는 것이 가장 좋습니다.)
좀 더 생각한 후, 풀링 디자인의 대체 특성이 있다고 생각합니다. $H$풀링 디자인이며 풀링 디자인의 일부 기능을 설명합니다. 특히 이것은 귀하의 답변에서 명제에 대한 간단한 증거를 제공합니다.
청구 3 $H$ 풀링 설계입니다. $x^*\not\subseteq y^*$ 모든 뚜렷한 $x,y\in V(H)$.
증명. ($\Rightarrow$) 별개의 존재가 있다고 가정 $x,y\in V(H)$ 그런 $x^*\subseteq y^*$. 그때$y^*=\{x,y\}^*$ 따라서 $H$ 풀링 디자인이 아닙니다.
($\Leftarrow$) 가정 $H$풀링 설계가 아닙니다. 즉, 존재한다고 가정합니다.$y\in V(H)$ 과 $Y\subseteq V(H)$ 와 $Y\neq \{y\}$ 그런 $y^*=Y^*$. 이후$Y\neq \{y\}$, 존재 $x\in Y$ 그런 $x\neq y$. 이후$x\in Y$, 우리는 $x^*\subseteq Y^*=y^*$. $\square$
추론 1 Let$H$ 하이퍼 그래프이고 $G$ 이중이다 $H$. $H$ 풀링 설계입니다. $e\not\subseteq f$ 모든 뚜렷한 $e,f\in E(G)$.
증명. ($\Rightarrow$) 가정 $H$풀링 디자인입니다. 구별 선택$e,f\in E(G)$ 구별되는 $x, y\in V(H)$각기. 이후$x^*\not\subseteq y^*$, 우리는 $e\not\subseteq f$.
($\Leftarrow$) 가정 $e\not\subseteq f$ 모든 뚜렷한 $e,f\in E(G)$. 구별 선택$x,y\in V(H)$ 구별되는 $e,f\in E(G)$. 이후$e\not\subseteq f$, 우리는 $x^*\not\subseteq y^*$. $\square$
추론 2 Let$H$ 하이퍼 그래프가되다 $e$ 가장자리 및 $n$ 다음과 같은 정점 $\binom{e}{\lfloor{e/2}\rfloor}<n$. 그때$H$ 풀링 디자인이 아닙니다.
증명. 허락하다$G$ 이중이다 $H$ 그리고 $G$ 있다 $e$ 정점 및 $n$가장자리. 이후$|E(G)|=n>\binom{e}{\lfloor{e/2}\rfloor}=\binom{|V(G)|}{\lfloor{|V(G)|/2}\rfloor}$, 슈 페르 너의 정리는 구별이 존재 함을 의미한다$e,f\in E(G)$ 그런 $e\subseteq f$. 그러므로$H$ Corollary 1의 풀링 디자인이 아닙니다. $\square$
특히 이것은 모든 풀링 디자인이 $4\leq n\leq 6$ 정점에는 최소 4 개의 가장자리가 있으며 모든 풀링 디자인은 $7\leq n\leq 10$ 정점에는 최소 5 개의 가장자리가 있습니다.
업데이트 2 .
다시 한 번, 좀 더 고려한 후에는 하이퍼 그래프의 설정에 머무르는 것이 더 분명하다고 생각합니다. $G$ 듀얼을 사용하는 것은 잊어 버리세요.
예를 들어, $K_8$-하이퍼 큐브 디자인에 $D=3$. 에서$K_8$-디자인, 각 모서리는 샘플 (28 개 있음), 각 꼭지점은 해당 꼭지점에 입사하는 샘플 (8 개 있음)을 풀링하는 테스트이며, 각 테스트는 7 개 샘플 (각 꼭지점의 정도가 7이므로), 각 샘플은 두 번 사용됩니다. $K_8$2-uniform). 댓글에서 언급했듯이 이것은$D=3$모든 매개 변수의 하이퍼 큐브 디자인. 또한 정확히 하나의 샘플이 감염된 경우$\{i,j\}$, 정확히 두 개의 테스트 (테스트 $i$ 및 테스트 $j$) 긍정적으로 돌아올 것입니다.
또 다른 예를 들어, $K_{13}$-하이퍼 큐브 디자인에 $D=4$. 그만큼$D=4$하이퍼 큐브 디자인은 각각 크기가 27이고 각 샘플이 4 번 사용되는 12 개의 테스트를 사용하여 81 개의 샘플을 처리합니다. 그만큼$K_{13}$-design은 13 개의 테스트를 사용하여 78 개의 샘플을 처리하지만 각 테스트의 크기는 12이고 각 샘플은 2 번만 사용됩니다.
마지막 예를 들어, $K_{9,9}$-설계 (즉, 각 부분에 9 개의 꼭지점이있는 완전한 이분 그래프) $D=4$하이퍼 큐브 디자인. 그만큼$K_{9,9}$-디자인은 각각 크기가 9이고 각 샘플이 2 회 사용되는 18 개의 테스트를 사용하여 81 개의 샘플을 처리합니다. 그러나이 디자인에는 세 번의 테스트가 양성으로 돌아 오면 어떤 두 샘플이 감염되었는지 정확히 알 수있는 추가 기능이 있습니다. 둘 다$K_{13}$-디자인도 $D=4$ 하이퍼 큐브 디자인에는 그 속성이 있습니다.
업데이트 3
풀링 설계에 대한 이러한 대안 적 사고 방식을 고려할 때 $G$ 가장 큰 정수로 정의 할 수 있습니다. $c$ 가장자리가 없도록 $e\in E(G)$ 최대의 조합에 포함 $c$ 가장자리 $E(G)\setminus \{e\}$. 따라서 테스트 용량이있는 풀링 설계를 원한다면$c$ 사용하는 $t$ 테스트, 우리는 하이퍼 그래프를 원합니다 $t$ 가장자리가 없도록 가능한 한 많은 가장자리가있는 정점 $e\in E(G)$ 최대의 조합에 포함 $c$ 가장자리 $E(G)\setminus \{e\}$. 이 문제는 Paul Erdős에서 연구되었다는 것이 밝혀졌습니다 . Frankl, P .; Füredi, Z. , 집합이 (r) 다른 사람의 합집합에 포함되지 않는 유한 집합의 가족 , Isr. J. Math. 51, 79-89 (1985). ZBL0587.05021 .
COVID-19의 현실적인 문제에 대해 생각하고 있다면 수학적 질문과 다릅니다. 나는 진짜 질문에 대한 요약을 만들려고했다.https://arxiv.org/pdf/2005.02388.pdf
이 질문을 답변으로 표시 할 수 있도록이 답변을 추가합니다. 제가 짐작 했어야했던 것처럼 이러한 문제는 70 년 이상 연구되어 왔으며 제가 요청한 질문은 아마도 약간의 변화까지 해결되거나 열려있는 것으로 알려져 있습니다. 여기에서 질문 한 질문 ( "조합 그룹 테스트"관련)과 관련된 참고 자료는 다음과 같습니다.
Du, D., Hwang, FK, & Hwang, F. (2000). 조합 그룹 테스트 및 그 응용 (Vol. 12). 세계 과학.
(이 언급을 나에게 알려준 Louis D에게 감사합니다.)
그러나 실질적인 문제는 오히려 "사소한 2 단계 알고리즘"을 사용하는 확률 적 그룹 테스트입니다 (더 많은 단계는 비실용적이며 가장 중요한 것은 결과를 제공하기에는 너무 길고 순전히 비 적응 알고리즘은 일반적으로 허용되지 않는 오류를 남깁니다). 최적의 성능은 대량의 제한과 제로 보급률로 알려져 있습니다.
Mézard, M. 및 Toninelli, C. (2011). 무작위 풀을 사용한 그룹 테스트 : 최적의 2 단계 알고리즘. 정보 이론에 대한 IEEE 트랜잭션, 57 (3), 1736-1745.
이 백서의 인상적인 점은 2 단계 알고리즘이 정보 이론이 다소 겸손한 (최적의 것으로 입증 된) 상수에 묶인 정보 이론을 달성한다는 것입니다.
최근 설문 조사는
Aldridge, M., Johnson, O. 및 Scarlett, J. (2019). 그룹 테스트 : 정보 이론 관점. arXiv 프리 프린트 arXiv : 1902.06002.
이 모든 것은 고정 된 보급의 경우 가장 좋은 (또는 최적에 가까운) 2 단계 알고리즘을 식별하는 것과 같은 몇 가지 중요한 실제 질문을 열어 두는 것 같습니다 .
흥미로운 방향은 [EFF] (Erdős, Paul; Frankl, P .; Füredi, Z., Families of finite sets of finite sets in which set is not covered by the union of (r) others, Isr. J)를 언급하는 @LouisD의 답변에서 밝혀졌습니다. . Math. 51, 79-89 (1985). ZBL0587.05021), 가족을 찾는 것입니다. $V$ 의 $k$-하위 집합 $n$-세트 $E$, 패밀리의 두 요소가 $t$포인트들. 그런 다음 각 하위 집합을 테이크에 연결하고$E$ 풀에, 우리는 최소한 탐지 능력을 가진 풀링 디자인을 얻습니다. $\lceil \frac k t\rceil-1$ 적어도 필요하기 때문에 $\lceil \frac k t\rceil$ 다른 요소를 포함하도록 패밀리의 요소.
이를 위해 여러 가지 방법으로 유한 필드를 사용할 수 있습니다. 예를 들어 투영 공간의 두 줄이 $\mathbb{F}_q$ 기껏해야 교차 $1$ 점 (다른 차원으로 일반화 할 수 있음).
이 방법으로 얻을 수있는 매우 효과적인 풀링 디자인 중에서 이전에 다른 anwsers에서 설명한 것과 동일하지 않은 두 가지를 언급하겠습니다.
1.1. 중히 여기다$E=\mathbb{F}_3^3$ 과 $V$아핀 라인 세트. 그런 다음 우리는$v=117$, $e=27$ 과 $c=2$.
1.2 고려$E=\mathbb{P}^3\mathbb{F}_3^4$ 과 $V$(투영) 라인 세트. 그런 다음 우리는$v=130$, $e=40$ 과 $c=2$.
매우 높은 압축률은 $2$-비행기 $4$그러나 탐지 능력은 보통 수준을 유지하며 낮은 유병률에서만 적용 가능한 것으로 보입니다. 압축률은 낮지 만 감지 용량은 크게$q$ 차원에서 작업 $2$.
편집하다. 계산이 잘못된 다른 방법을 제거했습니다.