{
  "id": "1511.04739",
  "version": "v1",
  "published": "2015-11-15T17:56:47.000Z",
  "updated": "2015-11-15T17:56:47.000Z",
  "title": "Counting dense connected hypergraphs via the probabilistic method",
  "authors": [
    "Béla Bollobás",
    "Oliver Riordan"
  ],
  "comment": "37 pages, 1 figure",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on $[n]=\\{1,2,\\ldots,n\\}$ with $m$ edges, whenever $n\\to\\infty$ and $n-1\\le m=m(n)\\le \\binom{n}{2}$. We give an asymptotic formula for the number $C_r(n,m)$ of connected $r$-uniform hypergraphs on $[n]$ with $m$ edges, whenever $r\\ge 3$ is fixed and $m=m(n)$ with $m/n\\to\\infty$, i.e., the average degree tends to infinity. This complements recent results of Behrisch, Coja-Oghlan and Kang (the case $m=n/(r-1)+\\Theta(n)$) and the present authors (the case $m=n/(r-1)+o(n)$, i.e., `nullity' or `excess' $o(n)$). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use `smoothing' techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-15T17:56:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C65",
      "05C30"
    ],
    "keywords": [
      "counting dense connected hypergraphs",
      "probabilistic method",
      "asymptotic formula",
      "bivariate local limit theorem",
      "average degree tends"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151104739B"
    }
  }
}