Geodesic
Maximum height of arbitrary classes of $(0,1)$-matrices and some of its applications
Sbornik. Mathematics, Tome 21 (1973) no. 3, pp. 467-484 
V. E. Tarakanov. Maximum height of arbitrary classes of $(0,1)$-matrices and some of its applications. Sbornik. Mathematics, Tome 21 (1973) no. 3, pp. 467-484. http://geodesic.mathdoc.fr/item/SM_1973_21_3_a8/
@article{SM_1973_21_3_a8,
     author = {V. E. Tarakanov},
     title = {Maximum height of~arbitrary classes of $(0,1)$-matrices and some of its applications},
     journal = {Sbornik. Mathematics},
     pages = {467--484},
     year = {1973},
     volume = {21},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_1973_21_3_a8/}
}
TY  - JOUR
AU  - V. E. Tarakanov
TI  - Maximum height of arbitrary classes of $(0,1)$-matrices and some of its applications
JO  - Sbornik. Mathematics
PY  - 1973
SP  - 467
EP  - 484
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SM_1973_21_3_a8/
LA  - en
ID  - SM_1973_21_3_a8
ER  - 
%0 Journal Article
%A V. E. Tarakanov
%T Maximum height of arbitrary classes of $(0,1)$-matrices and some of its applications
%J Sbornik. Mathematics
%D 1973
%P 467-484
%V 21
%N 3
%U http://geodesic.mathdoc.fr/item/SM_1973_21_3_a8/
%G en
%F SM_1973_21_3_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] D. R. Fulkerson, H. J. Ryser, “Widths and heights of $(0,1)$-matrices”, Canad. J. Math., 13 (1961), 239–255 | MR | Zbl

[2] D. R. Fulkerson, H. J. Ryser, “Multiplicities and minimal widths for $(0,1)$-matrices”, Canad. J. Math., 14 (1962), 498–508 | MR | Zbl

[3] D. R. Fulkerson, H. J. Ryser, “Widths sequences for special classes of $(0,1)$-matrices”, Canad. J. Math., 15 (1963), 371–396 | MR | Zbl

[4] G. Dzh. Raizer, Kombinatornaya matematika, izd-vo «Mir», Moskva, 1966

[5] A. A. Korbut, Yu. Yu. Finkelshtein, Diskretnoe programmirovanie, Moskva, 1969 | Zbl

[6] A. O. Gelfond, “O nekotorykh kombinatornykh svoistvakh $(0,1)$-matrits”, Matem. sb., 75(117):1 (1968), 3 | MR | Zbl

[7] V. E. Tarakanov, “O maksimalnoi glubine odnogo klassa $(0,1)$-matrits”, Matem. sb., 75 (117) (1968), 4–14 | MR | Zbl

[8] V. E. Tarakanov, “Sootnosheniya maksimalnykh glubin klassov kvadratnykh $(0,1)$-matrits pri razlichnykh parametrakh”, Matem. sb., 77 (119) (1968), 59–70 | MR | Zbl

[9] O. Ore, Teoriya grafov, izd-vo «Nauka», Moskva, 1968 | MR