On the upper bounds of the minimum number of rows of disjunct matrices

A 0-1 matrix is d-disjunct if no column is covered by the union of any d other columns. A 0-1 matrix is (d; z)-disjunct if for any column C and any d other columns, there exist at least z rows such that each of them has value 1 at column C and value 0 at all the other d columns. Let t(d, n) and t(d, n; z) denote the minimum number of rows required by a d-disjunct matrix and a (d; z)-disjunct matrix with n columns, respectively. We give a very short proof for the currently best upper bound on t(d, n). We also generalize our method to obtain a new upper bound on t(d, n; z). The work of Y. Cheng and G. Lin is supported by Natural Science and Engineering Research Council (NSERC) of Canada, and the Alberta Ingenuity Center for Machine Learning (AICML) at the University of Alberta. The work of D.-Z. Du is partially supported by National Science Foundation under grant No.CCF0621829.