Exact bounds for (λ, n)–stable 0-1 matrices.

Document Type: Research Paper




Consider a v × v (0, 1) 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 0. If A is (λ, n)–stable, λ, n ≥ 2,
then under suitable conditions on A, v ≥ k k(n−1)+(λ−2) . The case n λ−2
of equality leads to new and substantive connections with block designs. The previous bound and characterization of (λ, 2)–stable matrices follows immediately as a special case.


Main Subjects