Counting connected graphs and hypergraphs via the probabilistic method

DOI10.1002/RSA.20160MaRDI QIDQ5433264zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani

Publication date 8 January 2008

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

Full work available at URL https://doi.org/10.1002/rsa.20160

zbMATH Keywords

connectivitygiant componentprobabilistic methodrandom graphsrandom hypergraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The asymptotic number of connected \(d\)-uniform hypergraphs
• Counting dense connected hypergraphs via the probabilistic method
• Counting connected hypergraphs via the probabilistic method
• The number of connected sparsely edged uniform hypergraphs

Cited in

(19)

• The number of connected sparsely edged uniform hypergraphs
• Strictly balanced uniform hypergraphs and generalizations of zero-one law
• Counting sparse \(k\)-edge-connected hypergraphs with given number of vertices and edges
• The order of the giant component of random hypergraphs
• Asymptotic normality of the size of the giant component in a random hypergraph
• Swendsen-Wang algorithm on the mean-field Potts model
• Counting dense connected hypergraphs via the probabilistic method
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Corrigendum to: ``The asymptotic number of connected \(d\)-uniform hypergraphs
• Counting connected hypergraphs via the probabilistic method
• Local limit theorems for the giant component of random hypergraphs
• The asymptotic number of connected \(d\)-uniform hypergraphs
• A probabilistic counting lemma for complete graphs
• Birth and growth of multicyclic components in random hypergraphs
• Connectivity of random hypergraphs with a given hyperedge size distribution
• Mean-field Potts and random-cluster dynamics from high-entropy initializations
• Exploring the sharp propagation connectivity threshold in hypergraphs
• A method for generating connected Erdős-Rényi random graphs
• Counting connected graphs asymptotically

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

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