### Random Sparse Unary Predicates

by Shelah and Spencer. [ShSp:432]

Random Structures \& Algorithms, 1994

The main result is the following
Theorem: Let p=p(n) be such that p(n) in [0,1] for all n and
either p(n)<< n^{-1} or for some positive integer k,
n^{-1/k}<< p(n)<< n^{-1/(k+1)} or for all epsilon >0,
n^{- epsilon}<< p(n) and n^{- epsilon}<< 1-p(n) or for some
positive integer k, n^{-1/k}<< 1-p(n)<< n^{-1/(k+1)} or
1-p(n)<< n^{-1} . Then p(n) satisfies the Zero-One Law for
circular unary predicates. Inversely, if p(n) falls into none of
the above categories then it does not satisfy the Zero-One Law for
circular unary predicates.

Back to the list of publications