Asymptotic enumeration of sparse 0–1 matrices with irregular row and column sums

Let s=(s1,…,sm) and t=(t1,…,tn) be vectors of non-negative integer-valued functions with equal sum . Let N(s,t) be the number of m×n matrices with entries from {0,1} such that the ith row has row sum si and the jth column has column sum tj. Equivalently, N(s,t) is the number of labelled bipartite graphs with degrees of the vertices in one side of the bipartition given by s and the degrees of the vertices in the other side given by t. We give an asymptotic formula for N(s,t) which holds when S→∞ with 1⩽st=o(S2/3), where and . This extends a result of McKay and Wang [Linear Algebra Appl. 373 (2003) 273–288] for the semiregular case (when si=s for 1⩽i⩽m and tj=t for 1⩽j⩽n). The previously strongest result for the non-semiregular case required 1⩽max{s,t}=o(S1/4), due to McKay [Enumeration and Design, Academic Press, Canada, 1984, pp. 225–238].