Asymptotic enumeration of dense 0-1 matrices with specified line sums (Q2469197)

From MaRDI portal
Revision as of 23:20, 4 August 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    0 references
    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

    Identifiers