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

✍ Scribed by Brendan D. McKay; Xiaoji Wang

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 158 KB
• Volume: 373
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(03)00506-8

✦ Synopsis

Let s, t, m, n be positive integers such that sm = tn. Define N (s, t; m, n) to be the number of m × n matrices with entries from {0, 1}, such that each row sum is s and each column sum is t. Equivalently, N(s, t; m, n) is the number of labelled semiregular bipartite graphs, where one colour class comprises m vertices of degree s and the other comprises n vertices of degree t.

A sequence of earlier papers investigated the asymptotic behaviour of N(s, t; m, n) when m, n → ∞ with s and t comparatively small. The best result so far, due to McKay (1984), required s, t = o((sm) 1/4 ). In this paper, the analysis is improved to require only the weaker condition st = o(m 1/2 n 1/2 ).