Consider any matrix of zeros and ones with at most n ones in each row and fewer than (k + 1)n ones in all. Ossowski showed that, by deleting no more than k columns, one can get a matrix which contains no r x (n - r + 1) submatrix of ones for r = 1, 2, ..., n. We give a short proof of Ossowski's theorem in the slightly stronger form: any minimal set of columns, whose deletion has the desired effect, has cardinality at most k. (C) 1997 Academic Press.
展开▼
