Disjunct matrix

The following $6\backslash times\; 8$ matrix is 2-separable, because each pair of columns has a distinct sum. For example, the boolean sum (that is, the bitwise OR) of the first two columns is $110000\backslash or\; 001100\; =\; 111100$; that sum is not attainable as the sum of any other pair of columns in the matrix.

However, this matrix is not 3-separable, because the sum of columns 1, 2, and 3 (namely $111111$) equals the sum of columns 1, 4, and 5.

This matrix is also not $\backslash overline\{2\}$-separable, because the sum of columns 1 and 8 (namely $110000$) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be $\backslash overline\{d\}$-separable for any $d\backslash ge\; 1$.

\quad\left[

\begin{array}{cccccccc}

1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\

1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\

0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\

0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\

0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\

\end{array}

\right]

The following $6\backslash times\; 4$ matrix is $\backslash overline\{3\}$-separable (and thus 2-disjunct) but not 3-disjunct.

\quad\left[

\begin{array}{cccc}

1 & 0 & 0 & 1 \\

1 & 0 & 1 & 0 \\

0 & 1 & 1 & 0 \\

0 & 1 & 0 & 0 \\

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1 \\

\end{array}

\right]

There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum:

However, the sum of columns 2, 3, and 4 (namely $111111$) is a superset of column 1 (namely $110000$), which means that this matrix is not 3-disjunct.

{{main|Group testing}}

The non-adaptive group testing problem postulates that we have a test which can tell us, for any set of items, whether that set contains a defective item. We are asked to come up with a series of groupings that can exactly identify all the defective items in a batch of n total items, some d of which are defective.

A $d$-separable matrix with $t$ rows and $n$ columns concisely describes how to use t tests to find the defective items in a batch of n, where the number of defective items is known to be exactly d.

A $d$-disjunct matrix (or, more generally, any $\backslash overline\{d\}$-separable matrix) with $t$ rows and $n$ columns concisely describes how to use t tests to find the defective items in a batch of n, where the number of defective items is known to be no more than d.

For a given n and d, the number of rows t in the smallest d-separable $t\backslash times\; n$ matrix may (according to current knowledge) be smaller than the number of rows t in the smallest d-disjunct $t\backslash times\; n$ matrix, but in asymptotically they are within a constant factor of each other. Additionally, if the matrix is to be used for practical testing, some algorithm is needed that can "decode" a test result (that is, a boolean sum such as $111100$) into the indices of the defective items (that is, the unique set of columns that produce that boolean sum). For arbitrary d-disjunct matrices, polynomial-time decoding algorithms are known; the naïve algorithm is $O(nt)$. For arbitrary d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time.

Porat and Rothschild (2008) present a deterministic $O(nt)$-time algorithm for constructing a d-disjoint matrix with n columns and $\backslash Theta(d^2\backslash ln\; n)$ rows.

• Group testing
• Concatenated code
• Compressed sensing

{{cite journal |author1=Hong-Bin Chen |author2=Frank Hwang |date=2006-12-21 |title= Exploring the missing link among d-separable, {{overline|d}}-separable and d-disjunct matrices|journal=Discrete Applied Mathematics |volume=155 |issue=5 |pages=662–664 |doi=10.1016/j.dam.2006.10.009 | doi-access=free |citeseerx=10.1.1.848.5161 |mr = 2303978

}}

{{cite journal

| last1 = De Bonis | first1 = Annalisa

| last2 = Vaccaro | first2 = Ugo

| doi = 10.1016/S0304-3975(03)00281-0

| issue = 1–3

| journal = Theoretical Computer Science

| mr = 2000175

| pages = 223–243

| title = Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels

| volume = 306

| year = 2003}}

{{cite journal |author1=Paul Erdős |author2=Péter Frankl |author3=Zoltán Füredi |title=Families of finite sets in which no set is covered by the union of r others |journal=Israel Journal of Mathematics |volume=51 |issue=1–2 |pages=79–89 |year=1985 |issn=0021-2172|doi=10.1007/BF02772959 | doi-access=free |url=http://bsmath.hu/~p_erdos/1985-14.pdf}}

{{cite journal |author1=Piotr Indyk |author2=Hung Q. Ngo |author3=Atri Rudra |title=Efficiently Decodable Non-adaptive Group Testing |journal=Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA) |year=2010 |issn=1071-9040 |hdl=1721.1/63167}}

{{cite journal |author1=Ely Porat |author2=Amir Rothschild |title=Explicit Non-Adaptive Combinatorial Group Testing Schemes |journal=Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP) |pages=748–759 |year=2008 |arxiv=0712.3876 |bibcode=2007arXiv0712.3876P }}

• Atri Rudra's book on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 201), Chapter [http://www.cse.buffalo.edu/~atri/courses/coding-theory/book/chapters/chap20.pdf 17] {{Webarchive|url=https://web.archive.org/web/20150402093930/http://www.cse.buffalo.edu/~atri/courses/coding-theory/book/chapters/chap20.pdf |date=2015-04-02 }}
• Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii [Problems of Information Transmission], 18(3), 7–13.
• Dýachkov, A. G., Rashad, A. M., & Rykov, V. V. (1989). Superimposed distance codes. Problemy Upravlenija i Teorii Informacii [Problems of Control and Information Theory], 18(4), 237–250.
• {{cite journal |last1=Füredi | first1=Zoltán | authorlink1=Zoltán Füredi |year=1996 |title=On r-Cover-free Families |journal=Journal of Combinatorial Theory | series=Series A |volume=73 |issue=1 |pages=172–173 |doi=10.1006/jcta.1996.0012|doi-access=free }}

Category:Combinatorics