On the maximal \(\alpha\)-depth of (0, 1)-matrices of Ryser classes (Q1385850)

An asymptotics of the maximal \(\alpha\)-depth of \(n\times m\) \((0,1)\)-matrices with \(k\) units in each column and \(s\) units in each row is found under some conditions. The problem on the maximal \(\alpha\)-depth of \((0,1)\)-matrices (i.e. matrices with elements 0 and 1) of the so-called Ryser classes has been known for a long time. These classes are characterized by two sets of numbers \(k_1,\dots, k_m\) and \(s_1,\dots, s_n\) that specify the number of units in rows and columns, respectively. In this work, we consider the class of such \(n\times m\) \((0,1)\)-matrices with \(k\) units in each column and \(s\) units in each row, i.e., at \(k_1= \dots=k_m= k\) and \(s_1=\dots= s_n= s\). Denote the class of such matrices by \(A(n,m,k,s)\). If no constraints are imposed on the sum of the elements of each row, this class, which consists of \(n\times m\) \((0,1)\)-matrices with \(k\) units in each column, is denoted merely by \(A(n,m,k)\). Let \(\alpha\) be a positive integer. The \(\alpha\)-depth of a \((0,1)\)-matrix \(A\) is the minimum number of rows of \(A\) such that in the submatrix made up of these rows, each column contains at least \(\alpha\) units. This quantity is usually designated as \(\varepsilon_\alpha (A)\). The maximal \(\alpha\)-depth of the Ryser class \(A(n,m,k,s)\) is the number \(\varepsilon_\alpha (n,m,k,s)\) defined as follows: \[ \varepsilon_\alpha (n,m,k,s)= \max_{A\in A(n,m,k,s)} \varepsilon_\alpha (A). \] Respectively, \[ \varepsilon_\alpha (n,m,k)= \max_{A\in A(n,m,k)} \varepsilon_\alpha (A). \] A general upper bound on the maximal \(\alpha\)-depth of a \((0,1)\)-matrix was obtained in [\textit{V. K. Leont'ev}, Mat. Zametki 15, 421-429 (1974; Zbl 0306.05011)]. In [\textit{N. N. Kuzyurin}, Prob. Kibern. 37, 19-56 (1980; Zbl 0464.05021)], an asymptotics of \(\varepsilon_\alpha (n,m,k)\) as \(n\to\infty\) was found under some conditions, and it was shown that almost all matrices of the class \(A(n,m,k)\) have a depth asymptotically equal to the maximal depth. However, proceeding from the class \(A(n,m,k)\) to the Ryser class \(A(n,m,k,s)\) is nontrivial. While the cardinality of the class \(A(n,m,k)\) can be found trivially, i.e., \(| A(n m,k)|= \binom nk^m\), the asymptotics of the number of matrices in the class \(A(n,m,k,s)\) can be found only under rather strong constraints on the growth of \(k\) and \(s\). The main result of this work is the determination (under some conditions) of the asymptotics of \(\varepsilon_\alpha (n,m,k,s)\), which is the maximal \(\alpha\)-depth of the Ryser class \(A(n,m,k,s)\), and the proof that this asymptotics coincides with that of the maximal depth of the class \(A(n,m,k)\).