Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-25T23:11:29.088Z Has data issue: false hasContentIssue false
  • English
  • Français

ASYMPTOTIC ENUMERATION OF SYMMETRIC INTEGER MATRICES WITH UNIFORM ROW SUMS

Part of: Special matrices Combinatorics

Published online by Cambridge University Press:  04 March 2012

BRENDAN D. MCKAY  and
JEANETTE C. MCLEOD
BRENDAN D. MCKAY
Affiliation:
Research School of Computer Science, Australian National University, Canberra ACT 0200, Australia (email: [email protected])
JEANETTE C. MCLEOD*
Affiliation:
Department of Mathematics and Statistics, University of Canterbury, Christchurch 8140, New Zealand (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We investigate the number of symmetric matrices of nonnegative integers with zero diagonal such that each row sum is the same. Equivalently, these are zero-diagonal symmetric contingency tables with uniform margins, or loop-free regular multigraphs. We determine the asymptotic value of this number as the size of the matrix tends to infinity, provided the row sum is large enough. We conjecture that one form of our answer is valid for all row sums. An example appears in Figure 1.

Keywords

symmetric matrixasymptotic enumerationcontingency tablemultigraphdegree sequence

MSC classification

Secondary: 05A16: Asymptotic enumeration 15B36: Matrices of integers
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 92 , Issue 3 , June 2012 , pp. 367 - 384
Copyright
Copyright © 2013 Australian Mathematical Publishing Association Inc.

References

[1]Barvinok, A. and Hartigan, J. A., ‘An asymptotic formula for the number of nonnegative integer matrices with prescribed row and column sums’ (2010), arXiv:0910.2477v2.Google Scholar
[2]Beck, M. and Robins, S., Computing the Continuous Discretely (Springer, New York, 2006).Google Scholar
[3]Bender, E. A. and Canfield, E. R., ‘The asymptotic number of labeled graphs with given degree sequences’, J. Combin. Theory, Ser. A 24 (1978), 296–307.CrossRefGoogle Scholar
[4]Brualdi, R. A., Combinatorial Matrix Classes (Cambridge University Press, Cambridge, 2006).CrossRefGoogle Scholar
[5]Canfield, E. R. and McKay, B. D., ‘Asymptotic enumeration of integer matrices with large equal row and column sums’, Combinatorica 30 (2010), 655–680.CrossRefGoogle Scholar
[6]De Loera, J. A., Haws, D., Hemmecke, R., Huggins, P., Tauzer, J. and Yoshida, R., A User’s Guide for LattE v1.1, 2003 and software package LattE, available online at http://www.math.ucdavis.edu/∼latte/.Google Scholar
[7]Greenhill, C. S. and McKay, B. D., ‘Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums’, Adv. Appl. Math. 41 (2008), 459–481.CrossRefGoogle Scholar
[8]McKay, B. D., ‘Applications of a technique for labelled enumeration’, Congr. Numer. 40 (1983), 207–221.Google Scholar
[9]McKay, B. D., ‘Subgraphs of dense random graphs with specified degrees’, Combin. Probab. Comput. 20 (2011), 413–433.CrossRefGoogle Scholar
[10]McKay, B. D.et al., Tables of counts of integer matrices, available online at http://cs.anu.edu.au/∼bdm/data/intmat.html.Google Scholar
[11]McKay, B. D. and Wormald, N. C., ‘Asymptotic enumeration by degree sequence of graphs of high degree’, European J. Combin. 11 (1990), 565–580.CrossRefGoogle Scholar
[12]Read, R. C., ‘Some enumeration problems in graph theory’, Doctoral Thesis, University of London, 1958.Google Scholar
[13]Stanley, R. P., ‘Linear homogeneous Diophantine equations and magic labelings of graphs’, Duke Math. J. 40 (1973), 607–632.CrossRefGoogle Scholar