Asymptotic enumeration of dense 0-1 matrices with specified line sums (Q2469197)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic enumeration of dense 0-1 matrices with specified line sums |
scientific article |
Statements
Asymptotic enumeration of dense 0-1 matrices with specified line sums (English)
0 references
4 February 2008
0 references
From the authors' abstract: ``Let \(\mathbf{s} =(s_1,s_2,\dots,s_m)\) and \(\mathbf{t} =(t_1,t_2,\dots,t_n)\) be vectors of non-negative integers with \(\sum_{i=1}^m s_i=\sum_{j=1}^n t_j\). Let \(B(s,t)\) be the number of \(m\times n\) matrices over \({0,1}\) with \(j\)th row sum equal to \(s_j\) for \(1\leq j\leq m\) and \(k\)th column sum equal to \(t_k\) for \(1 \leq k\leq n\). Equivalently, \(B(s,t)\) is the number of bipartite graphs with \(m\) vertices in one part with degrees given by \(\mathbf{s}\), and \(n\) vertices in the other part with degrees given by \(\mathbf{t}\). Most research on the asymptotics of \(B(s,t)\) has focused on the sparse case, where the best result is that of \textit{C. Greenhill, B. D. McKay} and \textit{X. Wang} [J. Comb. Theory, Ser. A 113, No. 2, 291--324 (2006; Zbl 1083.05007)]. In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums [\textit{E. R. Canfield} and \textit{B. D. McKay}, Electron. J. Comb. 12, No. 1, Research paper 29, 31 p., electronic only (2005; Zbl 1076.05006)]. This paper extends the analytic methods used in the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.'' The proof relies on an application of the multidimensional saddle-point method, but with very deep and highly delicate analysis.
0 references
saddle-point method
0 references
asymptotic enumeration
0 references
0-1 matrix
0 references
bipartite graph
0 references
random matrix
0 references
0 references