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

Brendan D. McKay; Xiaoji Wang

doi:10.1016/S0024-3795(03)00506-8

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

Brendan D. McKay^*, Xiaoji Wang

^*Corresponding author for this work

Research output: Contribution to journal › Conference article › peer-review

25 Citations (Scopus)

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/2n^1/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	https://doi.org/10.1016/S0024-3795(03)00506-8
Publication status	Published - 1 Nov 2003
Event	Combinatorial Matrix Theory Conference (POSTECH) - Pohang, Korea, Republic of Duration: 14 Jan 2002 → 17 Jan 2002

Access to Document

10.1016/S0024-3795(03)00506-8

Cite this

@article{a1be8971672e496da309f863ecd09053,

title = "Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums",

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).",

author = "McKay, {Brendan D.} and Xiaoji Wang",

year = "2003",

month = nov,

day = "1",

doi = "10.1016/S0024-3795(03)00506-8",

language = "English",

volume = "373",

pages = "273--287",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "SUPPL.",

note = "Combinatorial Matrix Theory Conference (POSTECH) ; Conference date: 14-01-2002 Through 17-01-2002",

}

TY - JOUR

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

AU - McKay, Brendan D.

AU - Wang, Xiaoji

PY - 2003/11/1

Y1 - 2003/11/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0141569517&partnerID=8YFLogxK

U2 - 10.1016/S0024-3795(03)00506-8

DO - 10.1016/S0024-3795(03)00506-8

M3 - Conference article

SN - 0024-3795

VL - 373

SP - 273

EP - 287

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - SUPPL.

T2 - Combinatorial Matrix Theory Conference (POSTECH)

Y2 - 14 January 2002 through 17 January 2002

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this