Asymptotic enumeration of hypergraphs by degree sequence. (English) Zbl 1506.05016
Summary: We prove an asymptotic formula for the number of \(k\)-uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we find a formula that is asymptotically equal to the number of \(d\)-regular \(k\)-uniform hypergraphs on \(n\) vertices provided that \(dn\le c\binom{n}{k}\) for a constant \(c>0\), and \(3 \leq k < n^C\) for any \(C<1/9\). Our results relate the degree sequence of a random \(k\)-uniform hypergraph to a simple model of nearly independent binomial random variables, thus extending the recent results for graphs due to the second and third author [“Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph”, Preprint, arXiv:1702.08373].
References:
| [1] | D. Altman, C. Greenhill, M. Isaev, and R. Ramadurai. A threshold result for loose Hamiltonicity in random regular uniform hypergraphs. J. Combin. Theory Ser. B, 142:307-373, 2020. 2 · Zbl 1437.05124 |
| [2] | S. Behrens, C. Erbes, M. Ferrara, S. G. Hartke, B. Reiniger, H. Spinoza, and C. Tomlinson. New results on degree sequences of uniform hypergraphs. Electron. J. Combin., 20(4):P14, 2013. 8 · Zbl 1295.05081 |
| [3] | E. A. Bender and E. R. Canfield. The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theory Ser. A, 24(3):296-307, 1978. 1 · Zbl 0402.05042 |
| [4] | V. Blinovsky and C. Greenhill. Asymptotic enumeration of sparse uniform hypergraphs with given degrees. European J. Combin., 51:287-296, 2016. 2, 4, 5 · Zbl 1321.05116 |
| [5] | V. Blinovsky and C. Greenhill. Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees. Electron. J. Combin., 23(3):P3.17, 2016. 2, 4, 5 · Zbl 1344.05073 |
| [6] | A. Cayley. A theorem on trees. Quart. J. Math., 23:376-378, 1889. 1 · JFM 21.0687.01 |
| [7] | C. Cooper, A. Frieze, M. Molloy, and B. Reed. Perfect matchings in random r-regular, s-uniform hypergraphs. Combin. Probab. Comput., 5(1):1-14, 1996. 2, 4, 5 · Zbl 0857.05075 |
| [8] | A. Dudek, A. Frieze, A. Ruciński, and M. Šileikis. Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity. J. Combin. Theory Ser. B, 122:719-740, 2017. 2 · Zbl 1350.05110 |
| [9] | A. Dudek, A. Frieze, A. Ruciński, and M. Šileikis. Approximate counting of regular hypergraphs. Inform. Process. Lett., 113(19-21):785-788, 2013. 2, 4, 5 · Zbl 1285.05092 |
| [10] | P. L. Erdős, C. Greenhill, T. R. Mezei, I. Miklós, D. Soltész, and L. Soukup. The mixing time of the swap switch Markov chains: a unified approach. arXiv:1903.06600, 2019. 2 |
| [11] | S. Janson, T. Łuczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. 11 · Zbl 0968.05003 |
| [12] | G. Kuperberg, S. Lovett, and R. Peled. Probabilistic existence of regular combinatorial structures. Geom. Funct. Anal., 27(4):919-972, 2017. 2, 5 · Zbl 1369.05024 |
| [13] | A. Liebenau and N. Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph. arXiv:1702.08373, 2017. 1, 2, 3, 6, 10, 12, 18 |
| [14] | C. McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, pages 148-188. Cambridge University Press, 1989. 10 · Zbl 0712.05012 |
| [15] | B. D. McKay. Asymptotics for symmetric 0-1 matrices with prescribed row sums. Ars Combin., 19(A):15-25, 1985. 1, 2 · Zbl 0568.05032 |
| [16] | B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin., 11(6):565-580, 1990. 1, 2, 5 · Zbl 0739.05043 |
| [17] | B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs with degrees o(n 1/2 ). Combinatorica, 11(4):369-382, 1991. 1, 2 · Zbl 0742.05047 |
| [18] | B. D. McKay and N. C. Wormald. The degree sequence of a random graph. I. The models. Random Structures & Algorithms, 11(2):97-117, 1997. 2, 3 · Zbl 0884.05081 |
| [19] | J. W. Moon. Counting labelled trees. Canadian Mathematical Congress, Montreal, 1970. 1 · Zbl 0214.23204 |
| [20] | R. C. Read. Some enumeration problems in graph theory. PhD thesis, University of London, 1959. 1 |
| [21] | N. C. Wormald. Some problems in the enumeration of labelled graphs. PhD thesis, University of Newcastle, 1978. 1 |
| [22] | J. Xi, R. Yoshida, and D. Haws. Estimating the number of zero-one multi-way tables via sequential importance sampling. Ann. Inst. Statist. Math., 65(4):763-783, 2013. 2 · Zbl 1329.62268 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
