Максимальная глубина произвольных классов $(0,1)$-матриц и некоторые ее применения

Полученная ранее автором оценка сверху максимальной глубины $\overline\varepsilon$ для некоторых классов $(0,1)$-матриц (РЖМат., 1968, 8В222) обобщается на произвольные классы матриц. Показано, что при некоторых естественных условиях $\overline\varepsilon/N\leqslant\ln n/n+O(1/n)$, $n\to\infty$, где $N$ – число столбцов в матрице, а $n$ – минимальное число единиц в столбце. Пусть $\overline\varepsilon(k,n,N)$ – максимальная глубина класса матриц с $N$ столбцами, $k$ единицами в каждой строке и $n$ – в каждом столбце. Доказано, что $\overline\varepsilon(n,n,N)\geqslant2\bigl[\frac N{n+1}\bigr]$, $\overline\varepsilon(2,3,N)=\bigl[\frac35N\bigr]$, $\overline\varepsilon(2,n,N)=\bigl[\frac23N\bigr]$ ($n$ – четно); $\bigl[\frac35N\bigr]\leqslant\overline\varepsilon(2,n,N)\leqslant\bigl[\frac{2n-1}{3n-1}N\bigr]$ ($n$ – нечетно); отсюда следуют оценки для некоторых констант теории графов.
Библиография: 9 названий.