2014/09/04 by Vladimir Blinovsky, Blinovsky, Vladimir, Catherine Greenhill +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Random Matrices and Applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1409.1314
openalex publication_date 2014/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥ 3, let r= r(n)≥ 3 be an integer and let \boldsymbolk = (k1,…, kn) be a vector of nonnegative integers, where each kj = kj(n) may depend on n. Let M = M(n) = ∑j=1n kj for all n≥ 3, and define the set I = \ n≥ 3 | r(n) divides M(n)\. We assume that I is infinite, and perform asymptotics as n tends to infinity along I. Our main result is an asymptotic enumeration formula for linear r-uniform hypergraphs with degree sequence \boldsymbolk. This formula holds whenever the maximum degree kmax satisfies r4 kmax4(kmax + 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.