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

DOI10.1016/J.AAM.2008.01.002zbMATH Open1193.05020arXiv0707.0340OpenAlexW2964165395MaRDI QIDQ953898FDOQ953898

Authors: Catherine Greenhill, Brendan D. McKay 

Publication date: 6 November 2008

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Let svec = (s_1,...,s_m) and vec = (t_1,...,t_n) be vectors of nonnegative integer-valued functions of m,n with equal sum S = sum_{i=1}^m s_i = sum_{j=1}^n t_j. Let M(svec, vec) be the number of m*n matrices with nonnegative integer entries such that the i-th row has row sum s_i and the j-th column has column sum t_j 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=max_i s_i and t=max_j t_j. Previous work has established the asymptotic value of M(svec, vec) as m,n oinfty with s and t bounded (various authors independently, 1971-1974), and when svec, vec are constant vectors with m/n,n/m,s/n >= c/log n for sufficiently large (Canfield and McKay, 2007). In this paper we extend the sparse range to the case st=o(S^(2/3)). The proof in part follows a previous asymptotic enumeration of 0-1 matrices under the same conditions (Greenhill, McKay and Wang, 2006). We also generalise the enumeration to matrices over any subset of the nonnegative integers that includes 0 and 1.

Full work available at URL: https://arxiv.org/abs/0707.0340

Recommendations

• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Asymptotic enumeration of integer matrices with large equal row and column sums
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Asymptotic enumeration of binary matrices with bounded row and column sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• ASYMPTOTIC ENUMERATION OF SYMMETRIC INTEGER MATRICES WITH UNIFORM ROW SUMS
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of lonesum matrices
• scientific article; zbMATH DE number 969973

zbMATH Keywords

contingency tablesasymptotic enumerationswitchingsnon-negative integer matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Contingency tables (62H17) Asymptotic enumeration (05A16)

Cites Work

• Title not available (Why is that?)
• Paths in graphs
• Combinatorics and commutative algebra
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• Sampling contingency tables
• Improved bounds for sampling contingency tables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The asymptotic number of integer stochastic matrices

Cited In (22)

• On the largest size of an antichain in the Bruhat order for \(\mathcal A (2k,k)\)
• Phase transition in random contingency tables with non-uniform margins
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• Asymptotic enumeration of integer matrices with large equal row and column sums
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Exchangeable pairs, switchings, and random regular graphs
• Regularity in Weighted Graphs: A Symmetric Function Approach
• Title not available (Why is that?)
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Matrices with prescribed row and column sums
• Chains and Antichains in the Bruhat Order for Classes of (0, 1)-Matrices
• On the number of contingency tables and the independence heuristic
• An approximation algorithm for counting contingency tables
• The maximal length of a chain in the Bruhat order for a class of binary matrices
• ASYMPTOTIC ENUMERATION OF SYMMETRIC INTEGER MATRICES WITH UNIFORM ROW SUMS
• Title not available (Why is that?)
• ASYMPTOTIC EVALUATION OF BOSONIC PROBABILITY AMPLITUDES IN LINEAR UNITARY NETWORKS IN THE CASE OF LARGE NUMBER OF BOSONS
• Asymptotic enumeration of linear hypergraphs with given number of vertices and edges
• Lower bounds for contingency tables via Lorentzian polynomials
• What does a random contingency table look like?

This page was built for publication: Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q953898)