Asymptotic enumeration of dense 0-1 matrices with specified line sums |
| |
Authors: | E Rodney Canfield Catherine Greenhill Brendan D McKay |
| |
Institution: | a Department of Computer Science, University of Georgia, Athens, GA 30602, USA b School of Mathematics and Statistics, University of New South Wales, Sydney 2052, Australia c Department of Computer Science, Australian National University, Canberra ACT 0200, Australia |
| |
Abstract: | Let s=(s1,s2,…,sm) and t=(t1,t2,…,tn) be vectors of non-negative integers with . Let B(s,t) be the number of m×n matrices over {0,1} with jth row sum equal to sj for 1?j?m and kth column sum equal to tk for 1?k?n. Equivalently, B(s,t) is the number of bipartite graphs with m vertices in one part with degrees given by s, and n vertices in the other part with degrees given by t. Most research on the asymptotics of B(s,t) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by 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. |
| |
Keywords: | Asymptotic enumeration Binary matrix Bipartite graph 0-1 matrix |
本文献已被 ScienceDirect 等数据库收录! |
|