{
  "id": "1404.5887",
  "version": "v2",
  "published": "2014-04-23T16:52:07.000Z",
  "updated": "2015-11-17T17:14:34.000Z",
  "title": "Counting connected hypergraphs via the probabilistic method",
  "authors": [
    "Béla Bollobás",
    "Oliver Riordan"
  ],
  "comment": "Expanded; asymptotics clarified - no significant mathematical changes. 67 pages (including appendix)",
  "doi": "10.1017/S0963548315000309",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on $[n]$ with $m$ edges, whenever $n$ and the nullity $m-n+1$ tend to infinity. Asymptotic formulae for the number of connected $r$-uniform hypergraphs on $[n]$ with $m$ edges and so nullity $t=(r-1)m-n+1$ were proved by Karo\\'nski and \\L uczak for the case $t=o(\\log n/\\log\\log n)$, and Behrisch, Coja-Oghlan and Kang for $t=\\Theta(n)$. Here we prove such a formula for any $r\\ge 3$ fixed, and any $t=t(n)$ satisfying $t=o(n)$ and $t\\to\\infty$ as $n\\to\\infty$. This leaves open only the (much simpler) case $t/n\\to\\infty$, which we will consider in future work. ( http://arxiv.org/abs/1511.04739 ) Our approach is probabilistic. Let $H^r_{n,p}$ denote the random $r$-uniform hypergraph on $[n]$ in which each edge is present independently with probability $p$. Let $L_1$ and $M_1$ be the numbers of vertices and edges in the largest component of $H^r_{n,p}$. We prove a local limit theorem giving an asymptotic formula for the probability that $L_1$ and $M_1$ take any given pair of values within the `typical' range, for any $p=p(n)$ in the supercritical regime, i.e., when $p=p(n)=(1+\\epsilon(n))(r-2)!n^{-r+1}$ where $\\epsilon^3n\\to\\infty$ and $\\epsilon\\to 0$; our enumerative result then follows easily. Taking as a starting point the recent joint central limit theorem for $L_1$ and $M_1$, we use smoothing techniques to show that `nearby' pairs of values arise with about the same probability, leading to the local limit theorem. Behrisch et al used similar ideas in a very different way, that does not seem to work in our setting. Independently, Sato and Wormald have recently proved the special case $r=3$, with an additional restriction on $t$. They use complementary, more enumerative methods, which seem to have a more limited scope, but to give additional information when they do work.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-23T16:52:07.000Z",
      "abstract": "In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on $[n]$ with $m$ edges, whenever $n$ and the nullity $m-n+1$ tend to infinity. Asymptotic formulae for the number of connected $r$-uniform hypergraphs on $[n]$ with nullity $t=(r-1)m-n+1$, where $m$ is the number of edges, were proved by Karo\\'nski and \\L uczak for the case $t=o(\\log n/\\log\\log n)$, and Behrisch, Coja-Oghlan and Kang for $t=\\Theta(n)$. Here we prove such a formula for any $r\\ge 3$ fixed, and any $t=t(n)$ satisfying $t=o(n)$ and $t\\to\\infty$ as $n\\to\\infty$. This leaves open only the (much simpler) case $t/n\\to\\infty$, which we will consider in future work. Our approach is probabilistic. Let $H^r_{n,p}$ denote the random $r$-uniform hypergraph on $[n]$ in which each edge is present independently with probability $p$. Let $L_1$ and $M_1$ be the numbers of vertices and edges in the largest component of $H^r_{n,p}$. We prove a local limit theorem giving an asymptotic formula for the probability that $L_1$ and $M_1$ take any given pair of values within the `typical' range, for any $p=p(n)$ in the supercritical regime, i.e., when $p=p(n)=(1+\\epsilon(n))(r-2)!n^{-r+1}$ where $\\epsilon^3n\\to\\infty$ and $\\epsilon\\to 0$; our enumerative result then follows easily. Taking as a starting point the recent joint central limit theorem for $L_1$ and $M_1$, we use smoothing techniques to show that `nearby' pairs of values arise with about the same probability, leading to the local limit theorem. Behrisch et al used similar ideas in a very different way, that does not seem to work in our setting. Independently, Sato and Wormald have recently proved the special case $r=3$ of our result, with an additional restriction on $t$. They use complementary, more enumerative methods, which seem to have a more limited scope, but to give additional information when they do work.",
      "comment": "60 pages (including appendix)",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-11-17T17:14:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C65",
      "05C30"
    ],
    "keywords": [
      "counting connected hypergraphs",
      "probabilistic method",
      "asymptotic formula",
      "local limit theorem",
      "uniform hypergraph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 67,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.5887B"
    }
  }
}