dorsal/arxiv
View SchemaAsymptotic Rate Bounds and Constructions for the Inclusive Variant of Disjunct Matrices
| Authors | Yuto Mizunuma, Yuichiro Fujiwara |
|---|---|
| Categories | |
| ArXiv ID | 2601.09362vv1 |
| URL | https://arxiv.org/abs/2601.09362 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Disjunct matrices, also known as cover-free families and superimposed codes, are combinatorial arrays widely used in group testing. Among their variants, those that satisfy an additional combinatorial property called inclusiveness form a special class suitable for computationally efficient and highly error-tolerant group testing under the general inhibitor complex model, a broad framework that subsumes practical settings such as DNA screening. Despite this relevance, the asymptotic behavior of the inclusive variant of disjunct matrices has remained largely unexplored. In particular, it was not previously known whether this variant can achieve an asymptotically positive rate, a requirement for scalable group testing designs. In this work, we establish the first nontrivial asymptotic lower bound on the maximum achievable rate of the inclusive variant, which matches the strongest known upper bound up to a logarithmic factor. Our proof is based on the probabilistic method and yields a simple and efficient randomized construction. Furthermore, we derandomize this construction to obtain a deterministic polynomial-time construction. These results clarify the asymptotic potential of robust and scalable group testing under the general inhibitor complex model.
{
"annotation_id": "99fad53b-1d46-44e3-9876-56918d83eed6",
"date_created": "2026-02-17T05:53:20.124000Z",
"date_modified": "2026-02-17T05:53:20.124000Z",
"file_hash": "b7ed77aacb6999f2f4b42812eece8729388533d881a298423acc07362d7f1397",
"private": false,
"record": {
"abstract": "Disjunct matrices, also known as cover-free families and superimposed codes, are combinatorial arrays widely used in group testing. Among their variants, those that satisfy an additional combinatorial property called inclusiveness form a special class suitable for computationally efficient and highly error-tolerant group testing under the general inhibitor complex model, a broad framework that subsumes practical settings such as DNA screening. Despite this relevance, the asymptotic behavior of the inclusive variant of disjunct matrices has remained largely unexplored. In particular, it was not previously known whether this variant can achieve an asymptotically positive rate, a requirement for scalable group testing designs. In this work, we establish the first nontrivial asymptotic lower bound on the maximum achievable rate of the inclusive variant, which matches the strongest known upper bound up to a logarithmic factor. Our proof is based on the probabilistic method and yields a simple and efficient randomized construction. Furthermore, we derandomize this construction to obtain a deterministic polynomial-time construction. These results clarify the asymptotic potential of robust and scalable group testing under the general inhibitor complex model.",
"arxiv_id": "2601.09362",
"authors": [
"Yuto Mizunuma",
"Yuichiro Fujiwara"
],
"categories": [
"cs.IT",
"cs.DM",
"math.CO",
"math.IT"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Asymptotic Rate Bounds and Constructions for the Inclusive Variant of Disjunct Matrices",
"url": "https://arxiv.org/abs/2601.09362",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4db8247e-2faa-4b89-b903-3381a63cc82a",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}