Asymptotic enumeration of sparse connected 3-uniform hypergraphs

2014/01/29 by Cristiane M. Sato, Sato, Cristiane M., Nick Wormald +1
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1401.7381

openalex publication_date 2014/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive an asymptotic formula for the number of connected 3-uniform hypergraphs with vertex set [N] and M edges for M=N/2+R as long as R satisfies R = o(N) and R=ω(N^1/3ln² N). This almost completely fills the gap in the range of M for which the formula is known. We approach the problem using an `inside-out' approach of an earlier paper of Pittel and the second author, for connected graphs. A key part of the method uses structural components of connected hypergraphs called cores and kernels. These are structural components of connected hypergraphs. Our results also give information on the numbers of them with a given number of vertices and edges, and hence their typical size in random connected 3-uniform hypergraphs with N vertices and M edges, for the range of M we consider.

Related

• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
• Asymptotic enumeration of linear hypergraphs with given number of vertices and edges
• Small Cores in 3-uniform Hypergraphs
• Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
• Sparse hypergraphs: new bounds and constructions