Counting connected hypergraphs via the probabilistic method

DOI10.1017/S0963548315000309MaRDI QIDQ5364270zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: 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 $m$ edges and so nullity $t=(r-1)m-n+1$ were proved by Karo'nski and L uczak for the case $t=o(logn/loglogn)$, and Behrisch, Coja-Oghlan and Kang for $t=Theta(n)$. Here we prove such a formula for any $rge3$ fixed, and any $t=t(n)$ satisfying $t=o(n)$ and $toinfty$ as $noinfty$. This leaves open only the (much simpler) case $t/noinfty$, which we will consider in future work. ( arXiv:1511.04739 ) Our approach is probabilistic. Let $H_{n,p}^r$ 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_{n,p}^r$. 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+epsilon(n))(r-2)!n^{-r+1}$ where $epsilo{n}^{3}noinfty$ and $epsilono0$; 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$, 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.

Recommendations

• Counting dense 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

Cites work

• scientific article; zbMATH DE number 3151315 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3638870 (Why is no real title available?)
• An elementary proof of the local central limit theorem
• Asymptotic enumeration of sparse 2-connected graphs
• Asymptotic normality of the size of the giant component in a random hypergraph
• Component structure in the evolution of random hypergraphs
• Counting connected graphs and hypergraphs via the probabilistic method
• Counting connected graphs inside-out
• Counting connected hypergraphs via the probabilistic method
• Counting dense connected hypergraphs via the probabilistic method
• Exploring hypergraphs with martingales
• Local Limit Theorems for the Giant Component of Random Hypergraphs
• Local limit theorems for the giant component of random hypergraphs
• The asymptotic number of connected \(d\)-uniform hypergraphs
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The number of connected sparsely edged graphs
• The number of connected sparsely edged graphs. II. Smooth graphs and blocks
• The number of connected sparsely edged graphs. III. Asymptotic results
• The number of connected sparsely edged graphs. IV large nonseparable graphs
• The number of connected sparsely edged uniform hypergraphs
• The order of the giant component of random hypergraphs
• The phase transition in a random hypergraph
• The phase transition in the cluster‐scaled model of a random graph

Cited in

(10)

• Exploring hypergraphs with martingales
• Counting connected hypergraphs via the probabilistic method
• The asymptotic number of connected \(d\)-uniform hypergraphs
• Counting connected graphs and hypergraphs via the probabilistic method
• A probabilistic counting lemma for complete graphs
• 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 dense connected hypergraphs via the probabilistic method
• Counting sparse \(k\)-edge-connected hypergraphs with given number of vertices and edges

This page was built for publication: Counting 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 Q5364270)