d-Disjunct matrices: bounds and Lova'sz Local Lemma
d-Disjunct matrices: bounds and Lova'sz Local Lemma
复制标题
d-析取矩阵：界限和 Lovasz 局部引理
DOI：
10.1016/s0012-365x(01)00452-6
复制
发表时间：
2002
影响因子：
0.8
通讯作者：
H. Yeh
中科院分区：
文献类型：
--
作者：
H. Yeh
如果任意d列的并集（或布尔和）不包含任何其他列，则二进制矩阵被称为d- disjunt。这些矩阵构成了非自适应群测试算法和二进制d叠加码的基础。设t（d,n）表示有n列的d分离矩阵的最小行数。在这篇笔记中，我们研究了t（d,n）的边界和它的变化。Lovász局部引理。Soc。j<e:1> nosbolyai 10 (1974) 609-627；概率方法（Probabilistic Method, Wiley, New York, 1992 (2nd Edition, 2000)）和其他概率方法被用来提取更好的边界。对于给定的随机t×n二进制矩阵，使用Stein-Chen方法从d- disjunt矩阵中测量它的“坏”程度。
A binary matrix is said to be d-disjunct if the union (or Boolean sum) of any d columns does not contain any other column. Such matrices constitute a basis for nonadaptive group testing algorithms and binary d-superimposed codes. Let t(d,n) denote the minimum number of rows for a d-disjunct matrix with n columns. In this note we study the bounds of t(d,n) and its variations. Lovász Local Lemma (Colloq. Math. Soc. Jãnos Bolyai 10 (1974) 609–627; The Probabilistic Method, Wiley, New York, 1992 (2nd Edition, 2000)) and other probabilistic methods are used to extract better bounds. For a given random t×n binary matrix, the Stein–Chen method is used to measure how ‘bad’ it is from a d-disjunct matrix.