On the upper bounds of the minimum number of rows of disjunct matrices (Q1024738): Difference between revisions

A 0-1 matrix, i.e. a matrix containing only `zeros' and `ones' as its entries, is \(d\)-disjunct if it has no column that can be covered by the union, means by the bitwise Boolean sum, of any \(d\) other columns. A 0-1 matrix is \((d;z)\)-disjunct if for any column \(C\) and any \(d\) other columns, there exists at least \(z\) rows such that each of them has value 1 at column \(C\) and value 0 at all the other \(d\) columns. Note that \(d\)-disjunct matrices are \((d;z)\)-disjunct with \(z=1\). The quantities \(t(d,n)\) or \(t(d,n;z)\) denote the minimum number of rows required for a 0-1 matrix with \(n\) columns to be \(d\)-disjunct or \((d;z)\)-disjunct, respectively. This paper deals with the upper bound for the quantities \(t(d,n)\) or \(t(d,n;z)\) and gives a short proof for the currently best upper bound on \(t(d,n)\). It also generalizes the results for the upper bound on \(t(d,n;z)\). The proof uses more general \(q\)-ary matrices, i.e. matrices containing only values from the set \(\{1,\dots,q\}\) as it entries. (Note that, using this definition, the 2-ary (binary) matrix contains only `ones' and `twos' and thus it does not represent a 0-1 matrix.) The proof is based on probabilisitic arguments.