TY - JOUR

T1 - Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums

AU - Greenhill, Catherine

AU - McKay, Brendan D.

PY - 2008/10

Y1 - 2008/10

N2 - Let s = (s1, ..., sm) and t = (t1, ..., tn) be vectors of nonnegative integer-valued functions of m, n with equal sum S = ∑i = 1m si = ∑j = 1n tj. Let M (s, t) be the number of m × n matrices with nonnegative integer entries such that the ith row has row sum si and the jth column has column sum tj for all i, j. Such matrices occur in many different settings, an important example being the contingency tables (also called frequency tables) important in statistics. Define s = maxi si and t = maxj tj. Previous work has established the asymptotic value of M (s, t) as m, n → ∞ with s and t bounded (various authors independently, 1971-1974), and when all entries of s equal s, all entries of t equal t, and m / n, n / m, s / n ≥ c / log n for sufficiently large c [E.R. Canfield, B.D. McKay, Asymptotic enumeration of integer matrices with large equal row and column sums, submitted for publication, 2007]. In this paper we extend the sparse range to the case s t = o (S2 / 3). The proof in part follows a previous asymptotic enumeration of 0-1 matrices under the same conditions [C. Greenhill, B.D. McKay, X. Wang, Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, J. Combin. Theory Ser. A, 113 (2006) 291-324]. We also generalise the enumeration to matrices over any subset of the nonnegative integers that includes 0 and 1.

AB - Let s = (s1, ..., sm) and t = (t1, ..., tn) be vectors of nonnegative integer-valued functions of m, n with equal sum S = ∑i = 1m si = ∑j = 1n tj. Let M (s, t) be the number of m × n matrices with nonnegative integer entries such that the ith row has row sum si and the jth column has column sum tj for all i, j. Such matrices occur in many different settings, an important example being the contingency tables (also called frequency tables) important in statistics. Define s = maxi si and t = maxj tj. Previous work has established the asymptotic value of M (s, t) as m, n → ∞ with s and t bounded (various authors independently, 1971-1974), and when all entries of s equal s, all entries of t equal t, and m / n, n / m, s / n ≥ c / log n for sufficiently large c [E.R. Canfield, B.D. McKay, Asymptotic enumeration of integer matrices with large equal row and column sums, submitted for publication, 2007]. In this paper we extend the sparse range to the case s t = o (S2 / 3). The proof in part follows a previous asymptotic enumeration of 0-1 matrices under the same conditions [C. Greenhill, B.D. McKay, X. Wang, Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, J. Combin. Theory Ser. A, 113 (2006) 291-324]. We also generalise the enumeration to matrices over any subset of the nonnegative integers that includes 0 and 1.

KW - Asymptotic enumeration

KW - Contingency tables

KW - Non-negative integer matrices

KW - Switchings

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

U2 - 10.1016/j.aam.2008.01.002

DO - 10.1016/j.aam.2008.01.002

M3 - Article

SN - 0196-8858

VL - 41

SP - 459

EP - 481

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 4

ER -