Asymptotic enumeration of linear hypergraphs with given number of vertices and edges

Brendan D. McKay, Fang Tian

Published 2019-08-17Version 1

For $n\geq 3$, let $r=r(n)\geq 3$ be an integer. A hypergraph is $r$-uniform if each edge is a set of $r$ vertices, and is said to be linear if two edges intersect in at most one vertex. In this paper, the number of linear $r$-uniform hypergraphs on $n\to\infty$ vertices is determined asymptotically when the number of edges is $m(n)=o(r^{-3}n^{ \frac32})$. As one application, we find the probability of linearity for the independent-edge model of random $r$-uniform hypergraph when the expected number of edges is $o(r^{-3}n^{ \frac32})$. We also find the probability that a random $r$-uniform linear hypergraph with a given number of edges contains a given subhypergraph.