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

Brendan D. McKay*, Fang Tian

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    4 Citations (Scopus)

    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.

    Original languageEnglish
    Article number102000
    JournalAdvances in Applied Mathematics
    Volume115
    DOIs
    Publication statusPublished - Apr 2020

    Fingerprint

    Dive into the research topics of 'Asymptotic enumeration of linear hypergraphs with given number of vertices and edges'. Together they form a unique fingerprint.

    Cite this