Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums

E. Rodney Canfield ; Brendan D. McKay

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

Let $s,\,t,\,m$ and $n$ be positive integers such that $sm=tn$. Let $B(m,s;n,t)$ be the number of $m\times n$ matrices over $\{0,1\}$ with each row summing to $s$ and each column summing to $t$. Equivalently, $B(m,s;n,t)$ is the number of semiregular bipartite graphs with $m$ vertices of degree $s$ and $n$ vertices of degree $t$. Define the density $\lambda=s/n=t/m$. The asymptotic value of $B(m,s;n,t)$ has been much studied but the results are incomplete. McKay and Wang (2003) solved the sparse case $\lambda(1-\lambda)=o\big((mn)^{-1/2}\big)$ using combinatorial methods. In this paper, we use analytic methods to solve the problem for two additional ranges. In one range the matrix is relatively square and the density is not too close to 0 or 1. In the other range, the matrix is far from square and the density is arbitrary. Interestingly, the asymptotic value of $B(m,s;n,t)$ can be expressed by the same formula in all cases where it is known. Based on computation of the exact values for all $m,n\le 30$, we conjecture that the same formula holds whenever $m+n\to\infty$ regardless of the density.

Détail

DOI : 10.37236/1926

Classification : 05A16, 05C30, 15B33
Mots-clés : bipartite graphs, saddle-point method