D-Disjunct matrices: Bounds and Lovâsz Local Lemma

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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 (/-superimposed codes. Let t(d,n) denote the minimum number of rows for a (/-disjunct matrix with n columns. In this note we study the bounds of t(d,n) and its variations. Lovdsz 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.

Original languageEnglish
Pages (from-to)97-107
Number of pages11
JournalDiscrete Mathematics
Volume253
Issue number1-3
DOIs
StatePublished - 6 Jun 2002

Keywords

  • D-disjunct matrix
  • Group testing
  • Lovâsz local lemma
  • Probabilistic method
  • Stein-Chen approximation theorem

Fingerprint

Dive into the research topics of 'D-Disjunct matrices: Bounds and Lovâsz Local Lemma'. Together they form a unique fingerprint.

Cite this