Counting dense connected hypergraphs via the probabilistic method

DOI10.1002/RSA.20762MaRDI QIDQ4684827zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 25 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.04739

zbMATH Keywords

local limit theoremsrandom hypergraphshypergraph enumeration

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Connectivity (05C40) Hypergraphs (05C65)

Abstract: In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on $[n]=1,2,ldots,n$ with $m$ edges, whenever $noinfty$ and $$. We give an asymptotic formula for the number $C_r(n,m)$ of connected $r$-uniform hypergraphs on $[n]$ with $m$ edges, whenever $rge3$ is fixed and $m=m(n)$ with $m/noinfty$, i.e., the average degree tends to infinity. This complements recent results of Behrisch, Coja-Oghlan and Kang (the case $m=n/(r-1)+Theta(n)$) and the present authors (the case $m=n/(r-1)+o(n)$, i.e., `nullity' or `excess' $o(n)$). 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. The arguments are much simpler than in the sparse case; in particular, we can use `smoothing' techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.

Recommendations

• Counting connected hypergraphs via the probabilistic method
• Counting connected graphs and hypergraphs via the probabilistic method
• The asymptotic number of connected \(d\)-uniform hypergraphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Local Limit Theorems for the Giant Component of Random Hypergraphs

Cited in

(10)

• Exploring hypergraphs with martingales
• Degree sequences of sufficiently dense random uniform hypergraphs
• Counting connected hypergraphs via the probabilistic method
• The asymptotic number of connected \(d\)-uniform hypergraphs
• Counting connected graphs and hypergraphs via the probabilistic method
• Counting connected graphs with large excess
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Counting sparse \(k\)-edge-connected hypergraphs with given number of vertices and edges

This page was built for publication: Counting dense connected hypergraphs via the probabilistic method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684827)