@article{bollobas2014counting, author = "B{\'e}la Bollob{\'a}s and Oliver Riordan", 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\$\backslash\$'nski and \$\backslash\$L uczak for the case \\$t=o(\backslash log n/\backslash log\backslash log n)\\$, and Behrisch, Coja-Oghlan and Kang for \\$t=\backslash Theta(n)\\$. Here we prove such a formula for any \\$r\backslash ge 3\\$ fixed, and any \\$t=t(n)\\$ satisfying \\$t=o(n)\\$ and \\$t\backslash to\backslash infty\\$ as \\$n\backslash to\backslash infty\\$. This leaves open only the (much simpler) case \\$t/n\backslash to\backslash 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+\backslash epsilon(n))(r-2)!n\^{}\{-r+1\}\\$ where \\$\backslash epsilon\^{}3n\backslash to\backslash infty\\$ and \\$\backslash epsilon\backslash 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.", journal = "ArXiv", month = "apr", number = "1404.5887", pages = "60", title = "{C}ounting connected hypergraphs via the probabilistic method", url = "http://arxiv.org/abs/1404.5887", year = "2014", }