Abstract:
Kolmogorov first showed that a broad family of events, often called tail events, in an infinite space have probability zero or one. For a sequence of discrete probability spaces the analogous result is that the limiting probability is either zero or one. We restrict (mostly) to graphs and consider properties A expressible in the First Order Theory. There the basic result was first shown by Glebskii, Kogan, Liagonkii and Talanov and later, independently, by Fagin: For the random graph $G(n, p(n))$ with $p = p(n)$ fixed and any first order property A the limiting (in $n$) probability of $A$ is either zero or one. Together with Shelah, this speaker showed that this Zero-One law also holds when $p = n-1$ and is an irrational number. Roughly (and not quite accurately) this means such $p = n-1$ are boring functions where nothing interesting is occurring. We examine Zero-One laws for Random Graphs and other sequences of discrete random structures. For other $p(n)$, such as $p(n) = n-1$ and $p(n) = \ln n$ while a Zero-One Law does not hold we are able to describe completely the possible limiting behaviors.
