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

Abstract

For n ≥ 3, let r = r(n) ≥ 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 → ∞ vertices is determined asymptotically when the number of edges is m(n) = o(r−3n3/2). 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−3n3/2). We also find the probability that a random r-uniform linear hypergraph with a given number of edges contains a given subhypergraph.