- Bollobás, Béla; Riordan, Oliver
- 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.
- Research areas:
- Year:
- 2014
- Type of Publication:
- Article
- Journal:
- ArXiv
- Number:
- 1404.5887
- Pages:
- 60
- Month:
- April

Hits: 5662