Abstract
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/2n1/2).
| Original language | English |
|---|---|
| Pages (from-to) | 273-287 |
| Number of pages | 15 |
| Journal | Linear Algebra and Its Applications |
| Volume | 373 |
| Issue number | SUPPL. |
| DOIs | |
| Publication status | Published - 1 Nov 2003 |
| Event | Combinatorial Matrix Theory Conference (POSTECH) - Pohang, Korea, Republic of Duration: 14 Jan 2002 → 17 Jan 2002 |
Fingerprint
Dive into the research topics of 'Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver