Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees

Abstract

A hypergraph is simple if it has no loops and no repeated edges, and a hypergraph is linear if it is simple and each pair of edges intersects in at most one vertex. For $n\ge 3$, let $r=r(n)\ge 3$ be an integer and let $\mathbf{k}=(k_1,\dots ,k_n)$ be a vector of nonnegative integers, where each $k_j=k_j(n)$ may depend on $n$. Let $M=M(n)={\sum }_{j=1}^n{k}_j$ for all $n\ge 3$, and define the set $\mathcal{I}=\{n\ge 3\mid r(n)\text{ divides }M(n)\}$. We assume that $\mathcal{I}$ is infinite, and perform asymptotics as $n$ tends to infinity along $\mathcal{I}$. Our main result is an asymptotic enumeration formula for linear $r$-uniform hypergraphs with degree sequence $\mathbf{k}$. This formula holds whenever the maximum degree $k_{\max }$ satisfies $r^4{k}_{\max }^4(k_{\max }+r)=o(M)$. Our approach is to work with the incidence matrix of a hypergraph, interpreted as the biadjacency matrix of a bipartite graph, enabling us to apply known enumeration results for bipartite graphs. This approach also leads to a new asymptotic enumeration formula for simple uniform hypergraphs with specified degrees, and a result regarding the girth of random bipartite graphs with specified degrees.

arXiv comment18 pages, 3 figures. Paper revised after referees comments