Counting connected hypergraphs via the probabilistic method

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:
Type of Publication:
Hits: 5662

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information