Exact bounds for (λ,n)–stable ۰-۱ matrices.

Consider a v × v (۰, ۱) matrix A with exactly k ones in each row and each column. A is (λ, n)–stable, if it does not contain any λ × n submatrix with exactly one ۰. If A is (λ, n)–stable, λ, n ≥ ۲, then under suitable conditions on A, v ≥ k k(n−۱)+(λ−۲) . The case n λ−۲ of equality leads to new and substantive connections with block designs. The previous bound and characterization of (λ, ۲)–stable matrices follows immediately as a special case.

Keywords:

incidence matrices , block designs , (۰ , ۱) matrices