Asymptotic enumeration of hypergraphs by degree sequence

Counting discrete objects constitutes the foundations of combinatorics, with a history stretching back millennia. For instance, the factorial \(n!\), which as a concept originated as far back as 300 BCE, counts the number of bijective mappings between two \(n\)-element sets, and the binomial coefficient \({n\choose k}\) counts the number of \(k\)-element subsets of an \(n\)-element set. In graph theory, one of the most famous “counting” results is Cayley’s formula: the number of \(n\)-vertex (labelled) trees, or equivallently the number of spanning trees of the complete graph \(K_n\), is \(n^{n-2}\). Cayley’s formula has many elegant and short proofs. More generally, Moon’s formula asserts that the number of \(n\)-vertex trees with degree sequence \(d_1,\ldots,d_n\) is \({n-2\choose {d_1-1,\ldots,d_n-1}}\), which can be proven using a bijective argument based on Prüfer sequences. While exact formulas exist in the case of trees, more general graph counting scenarios turned out to be much more challenging. In particular, only an asymptotic formula exists for the number of \(d\)-regular \(n\)-vertex graphs (except for the trivial settings) and computing the number of spanning trees of a given input graph is a #P-complete problem. This papers concerns the more general setting of k-uniform hypergraphs and provides an asymptotic formula for the number of \(k\)-uniform hypergraphs with a given degree sequence for a wide range of parameters. In particular, the main result of the paper together with the result of Kuperberg, Lovett and Peled recently published in Geom. Funct. Anal. 27 (2017), 919–972 gives an asymptotic formula for the number of \(d\)-regular \(k\)-uniform hypergraphs for all values of \(d\).