Proc. RANDOM 2004
It is exponentially unlikely that a sparse random graph or hypergraph is connected, but such graphs occur commonly as the giant components of larger random graphs. 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 m=O(n) edges. 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) conditioned on its being connected. This generalizes prior work of Bender, Canfield, and McKay on the number of connected graphs; however, our approach relies on elementary probabilistic methods, extending an approach of O'Connell, rather than using powerful tools from enumerative combinatorics such as generating functions and complex analysis. We also estimate the probability for each t that, given k=O(n) balls in n bins, every bin is occupied by at least t balls.