Asymptotic Enumeration of Combinatorial Structures.

摘要

In a previous paper the author found and announced complete results on the asymptotic enumeration of (n,q) graphs, i.e. graphs with n unlabelled nodes and q edges. This year the proofs of these results have been shortened and simplified. The results themselves have been applied to obtain very precise theorems about the behaviour of the probability of connectedness of a graph for large fixed n as q increases. They have also been applied to extend theorems found by Erdos and Renyi about asymptotic graphs. The quite different problem of finding a sufficient condition that almost all (n,q) graphs are Hamiltonian has been open for some years. A solution is found,first for the corresponding problem for digraphs,which is easier,and then for the original problem. (Author)