Counting connected graphs and hypergraphs via the probabilistic method
While it is exponentially unlikely that a sparse random graph or hypergraph is connected, with probability 1 - o(1) such a graph has a "giant component" that, given its numbers of edges and vertices, is a uniformly distributed connected graph. This simple observation allows us to estimate the number of connected graphs, and more generally the number of connected d-uniform hypergraphs, on n vertices with ((d - 1)(-1) + epsilon)n   0 is arbitrarily small but independent of n. We also estimate the probability that a binomial random hypergraph H-d(n, p) is connected, and determine the expected number of edges of H-d(n, p) given that it is connected. This extends prior work of Bender et al. (Random Struct Algorithm 1 (1990), 127-169) on the number of connected graphs. While Bender et al. (1990) is based on a recursion relation satisfied by the number of connected graphs, so that the argument is to some extent enumerative, we present a purely probabilistic approach. (C) 2007 Wiley Periodicals, Inc.
connectivity probabilistic method random graphs giant component random hypergraphs