Jump to content

Talk:Disjunct matrix

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Example of 2-disjunct matrix with 12 columns

[edit]

The current article says, without further explanation,

If I understand correctly, this matrix encodes a way to detect 2 defective items among 12, in only 9 tests. However, there is a more efficient solution that uses only 8 tests instead of 9 tests. Namely, you can do this:

So what I don't understand about the current article is: What's the significance of ? Does it relate somehow to the preceding text in the article, e.g. was it constructed using some interesting algorithm? Or is it just a completely arbitrary example? (Or, it's possible that I've misunderstood the terms here and my matrix is "2-separable but not 2-disjunct," or something like that. I'm not clear on why we need two different terms; it seems like maybe only one of them has physical significance in non-adaptive group testing?) --Quuxplusone (talk) 05:51, 27 April 2019 (UTC)[reply]

Answering my own question from last year: Indeed, the 8x12 matrix I provided above is "2-separable but not 2-disjunct." That is, in group-testing terms, my 8x12 matrix can find exactly 2 defective items among 12 in only 8 tests; but the article's 9x12 matrix can find 0, 1, or 2 defective items among 12 — it turns out that we need an extra test if we want to accomplish that slightly harder goal.
I've radically rewritten the article to make the distinction between "d-separable" and "d-disjunct" more clear, and given it some fresh (and smaller) examples. --Quuxplusone (talk) 21:36, 2 January 2020 (UTC)[reply]

6x4 matrix is not 2-disjunct

[edit]

column set (3,4) has a boolean sum that is a superset of column 1.

104.218.66.41 (talk) 23:53, 8 May 2021 (UTC) josh[reply]