An extension of 0-1 laws

Let σ be a first-order sentence about graphs. For n ? ω let n^α, α ? 0, be the edge probability for the random graph on n vertices, and let pr(σ, n) be the probability that the random graph on n vertices, satisfies σ. If σ and σ satisfy certain conditons then either pr(σ,n)～βn^?γ for some β > 0 and γ ?0, or pr(σ,i)=o(n?γ) for all γ, In particular, this holds for all γ and irrational α. The result has implications for rapidly mixing Markov chains whose stags are finite structures. If the stationary distribution is the same as the for random graphs with edg probability n^?α, then the expected waiting time unitl σ holds (as a function of n) is either bounded above by a polynomial in n, or it grows faster than any polynomical. All these results easily extend to finite structures of any relational type. © 1994 John Wiley & Sons, Inc.