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

Document Type : Research Paper


Faculté de Médecine et des sciences de la santé, Université de Sherbrooke, Sherbrooke, Canada


Consider a $v \times v$ $(0,1)$ matrix $A$ with exactly $k$ ones in each row and each column. $A$ is $(\lambda, n)$--stable, if it does not contain any $\lambda \times n$ submatrix with exactly one $0$. If $A$ is $(\lambda, n)$--stable, $\lambda, n \ge 2$, then under suitable conditions on $A$, $v \ge \frac{k}{n} \frac{k(n -1)+(\lambda -2)}{\lambda -2}$. The case of equality leads to new and substantive connections with block designs. The previous bound and characterization of $(\lambda,2)$--stable matrices follows immediately as a special case.


Main Subjects

[1] R. P. Anstee, Properties of (0, 1)–Matrices with no triangles, Journal of Combinatorial Theory Series A, 29 (1980)
[2] R. P. Anstee and N. Kamoosi, Small Forbidden Configurations III, Electronic Journal of Combinatorics, 14 (2007).
[3] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Bibliographisches Institut, 1985.
[4] A. A. Bruen, Some new replaceable translation nets, Canadian Journal of Mathematics, 29 (1977) 225–237.
[5] A. A. Bruen and R. Silverman, Switching sets in P G(3, q), Proceedings American Math Society, 43 (1974) 176–180.
[6] A. A. Bruen, T. C. Bruen and R. Silverman, Incidence matrices with forbidden configurations, AMS Press, Providence
Rhode Island, 2010.
[7] A. A. Bruen and T. C. Bruen and R. Silverman, A characterization of (λ, 2) stable matrices, Linear Algebra and its
Applications, 436 (2012) 814–819.
[8] H. J. Ryser, Combinatorial configurations, SIAM Journal in Applied Mathematics, 17 (1969) 593–602.