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 C-r (n, t) are known only for partial ranges of the parameters: in 1997 Karonski and Luczak gave one for t = o(log n/log log n), and recently Behrisch, Coja-Oghlan and Kang gave one for t = T(n). Here we prove such a formula for any fixed r >= 3 and any t = t(n) satisfying t = o(n) and t -> infinity as n -> infinity, complementing the last result. This leaves open only the case t/n -> infinity, 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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1017/S0963548315000309 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Discrete mathematics,Graph,Asymptotic formula,Combinatorics,Central limit theorem,Vertex (geometry),Constraint graph,Hypergraph,Infinity,Probabilistic method,Mathematics | Journal | 25 |
Issue | ISSN | Citations |
SP1 | 0963-5483 | 2 |
PageRank | References | Authors |
0.44 | 7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Béla Bollobás | 1 | 2696 | 474.16 |
Oliver Riordan | 2 | 61 | 8.19 |