Asymptotic Rate Bounds and Constructions for the Inclusive Variant of Disjunct Matrices
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917203746488320 |
|---|---|
| author | Mizunuma, Yuto Fujiwara, Yuichiro |
| author_facet | Mizunuma, Yuto Fujiwara, Yuichiro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_09362 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Asymptotic Rate Bounds and Constructions for the Inclusive Variant of Disjunct Matrices Mizunuma, Yuto Fujiwara, Yuichiro Information Theory Discrete Mathematics Combinatorics 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. |
| title | Asymptotic Rate Bounds and Constructions for the Inclusive Variant of Disjunct Matrices |
| topic | Information Theory Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2601.09362 |