Maximum height of~arbitrary classes of $(0,1)$-matrices and some of its applications

V. E. Tarakanov

Sbornik. Mathematics, Tome 21 (1973) no. 3, pp. 467-484

Résumé

An upper estimate obtained earlier by the author for the maximum height $\overline\varepsilon$ of certain $(0,1)$-matrices (RZhMat., 1968, 8V222) is generalized to arbitrary classes of matrices. It is shown that under certain natural conditions $\overline\varepsilon/N\leqslant\ln n/n+O(1/n)$, $n\to\infty$, where $N$ is the number of columns in the matrix and $n$ is the maximum number of ones in a column. Let $\overline\varepsilon(k,n,N)$ be the maximum height of the class of matrices with $N$ columns, $k$ ones in each row and $n$ ones in each column. It is proved that $\overline\varepsilon(n,n,N)\geqslant2\bigl[\frac N{n+1}\bigr]$, $\overline\varepsilon(2,3,N)=\bigl[\frac35N\bigr]$, $\overlinevarepsilon(2,n,N)=\bigl[\frac23N\bigr]$ ($n$ even); $\bigl[\frac35N\bigr]\leqslant\overline\varepsilon(2,n,N)\leqslant\bigl[\frac{2n-1}{3n-1}N\bigr]$ ($n$ odd); from this follows estimates for some constants in graph theory. Bibliography: 9 titles.