Article contents
Counting Connected Hypergraphs via the Probabilistic Method
Published online by Cambridge University Press: 04 January 2016
Abstract
In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on [n] = {1,2,. . .,n} with m edges, whenever n and the nullity m−n+1 tend to infinity. Let Cr(n,t) be the number of connected r-uniform hypergraphs on [n] with nullity t = (r−1)m−n+1, where m is the number of edges. For r ≥ 3, asymptotic formulae for Cr(n,t) are known only for partial ranges of the parameters: in 1997 Karoński and Łuczak gave one for t = o(log n/log log n), and recently Behrisch, Coja-Oghlan and Kang gave one for t=Θ(n). Here we prove such a formula for any fixed r ≥ 3 and any t = t(n) satisfying t = o(n) and t→∞ as n→∞, complementing the last result. This leaves open only the case t/n→∞, which we expect to be much simpler, and will consider in future work. 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. We deduce this from the corresponding central limit theorem by smoothing techniques.
Keywords
- Type
- Paper
- Information
- Combinatorics, Probability and Computing , Volume 25 , Issue 1: Oberwolfach Special Issue Part 2 , January 2016 , pp. 21 - 75
- Copyright
- Copyright © Cambridge University Press 2015
References
- 3
- Cited by