A logical approach to asymptotic combinatorics I. First order properties (Q1103939): Difference between revisions

The author presents a general framework for dealing with some problems of asymptotic combinatorics. This framework provides methods for determining the probability that a large, finite structure, randomly chosen from a given class, will have a given property. The author's main concern is the asymptotic probability, that is the limiting value as the size of the structure increases. The author restricts the considerations to classes closed under disjoint unions and components. This condition is general enough to include the classes of graphs, permutations, unary functions and many other important examples. The main results of the paper are about classes satisfying this condition. The existence of asymptotic probabilities for a special set of sentences called component-bounded sentences is equivalent to a condition on the growth of such classes; necessary and sufficient conditions for every first order sentence to have an asymptotic probability of 0 or 1 in nonfast growing classes are given. The paper contains a long list of examples from the literature and some open questions.