Counting Connected Hypergraphs via the Probabilistic Method. (4th January 2016)

• Record Type: Journal Article
• Authors: BOLLOBÁS, BÉLA; RIORDAN, OLIVER
• Is Part Of: Combinatorics, probability and computing. Volume 25:Number 1(2016:Jan.)
• Page Start: 21
• Page End: 75
• Publication Date: 2016-01-04
• Subjects: Primary 05C80, -- Secondary 05C65, -- 05C30; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548315000309
• Languages: English
• ISSNs: 0963-5483

Abstract

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 C r ( 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 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.