0$ and exponential decay kills off polynomial
growth so the failure probability goes to zero.
The graphs $G$ modelling $T$ are said by Peter Winkler to have
the Alice's Restaurant property. Members of a certain generation
may remember the refrain: You can get anything you want at
Alice's Restaurant. All possible witnesses are there.
Let $G,G'$ model $T$. Duplicator's stategy is simplicity itself. Staying alive.
When $x_i$ is played in $G$ Duplicator looks for $x_i'\in G'$ with the
appropriate adjacencies to the previously selected vertices. By the Alice's
Restaurant property she never gets stuck.
\section{ Countable Models}
Whenever we have a Zero-One Law we have the complete theory $T$ of
those sentences holding almost surely. By the G\"odel Completeness
Theorem such a theory must have a finite or countable model. The
models cannot be finite since for every $r\geq 1$ the sentence ``There
exist distinct $x_1,\ldots,x_r$" is in the almost sure theory since it
holds for all $n\geq r$. Thus $T$ must have a countable model - in
our case a countable graph $G$. What does $G$ look like? The first
question is whether $G$ is unique - that is, whether $T$ is
$\aleph_0$-categorical.
Consider first the Alice's Restaurant theory $T$ for $p$ constant.
This is $\aleph_0$-categorical by an elegant argument. Let $G,G'$
be two countable models of $T$, both labelled by the positive integers.
We build up an isomorphism $\Phi:G\ra G'$ by alternating Left Stages
and Right Stages. After $n$ steps the map $\Phi$ will map $n$ elements
of $G$ into $n$ elements of $G'$ preserving adjacency and nonadjacency.
For a Left Stage let $x$ be the least element of $G$ for which $\Phi(x)$
is not defined. We require of $\Phi(x)$ that for any $a\in G$ for which
$\Phi(a)$ has been defined we want $\Phi(x)$ to be either adjacent or
nonadjacent to $\Phi(a)$ depending on whether $x$ is adjacent or
nonadjacent to $a$. By Alice's Restaurant we can find such an $x'$.
In the Right Stage we reverse the roles of $G,G'$. Let $x'$ be the least
element of $G'$ for which $\Phi^{-1}(x')$ is not defined and find
$x=\Phi^{-1}(x')$ with the appropriate adjacencies. By step $2n$
vertices $1,\ldots,n$ have been used up in both $G$ and $G'$ so that
at the end of this infinite process all vertices have been used up and
$\Phi$ is a bijection giving the desired isomorphism. The
countable graph $G$ satisfying Alice's Restaurant is sometimes called
the Rado graph in honor of the late Richard Rado.
What about the theory $T_{\ah}$ for $0<\ah<1$ irrational. This is
not $\aleph_0$-categorical. We indicate two arguments that create
(well, prove the existence) of different countable models.
Consider
rigid extensions with $r=1$, so of the form $(\{x\},H)$, with
parameters $v,e$ where $(\emptyset,H)$ is safe. (With $\ah=\pi/7$
an example is $H=K_5$.) For such $H$ almost surely there exist copies
of $H$ but most vertices do not lie in such copies. Suppose
$(\{x\},H_i)$ is an sequence of such extensions with parameters
$v_i,e_i$. For any $s$ define the graph $H^s$ to be the
of $H_1,\ldots,H_s$ considered as disjoint vertex sets except
for the common vertex $x$. Suppose further that there almost surely
exists a copy of $H^s$.
Such a sequence can be shown to exist for any $\ah$ by employing
a little number theory. The key is to find $v_i,e_i$ such that
$v_i-e_i\ah$ is only very slightly negative. Now we can create a
model in which some element is in a copy of $H^s$ for all $s$. We
add a constant symbol $c$ to our logic and add the infinite schema
(for $s\geq 1$) that $c$ is in a copy of $H^s$. Any finite segment
of this system is consistent since in $T$ itself one has that there
exists a copy of $H^s$. By compactness there exists a model and
the element corresponding to $c$ has the desired property.
Now we create a special countable graph $G_{\ah}$ that models
$T_{\ah}$. The vertices will be the positive integers. For
every safe rooted graph $(R,H)$ and every $r=|R|$ distinct integers
$\vec{x}=(x_1,\ldots,x_r)$ consider the {\em witness demand}
that there must exist $\vec{y}=(y_1,\ldots,y_v)$ forming an $(R,H)$
extension over $\vec{x}$. Witness demands would include, continuing with
our standard $\ah=\pi/7$ example,
that there exists $y_1$ adjacent to $167,233$ or that there exist
$y_1,y_2,y_3$ forming a $K_4$ with $26$. We include the case $R=\emptyset$
so that one demand is that there exist $y_1,y_2$ forming an edge.
Turn the witness demands into a countable list. Now satisfy them one by
one using new points in a minimal way
. That is, when we need $y_1$ adjacent to $167,233$ pick a vertex, say
$23801$ that has not been touched before (at any stage only a finite
number of points have been touched) and join it to $167,233$ and nothing
else. There are two very nice properties of this construction. First
$G_{\ah}$ is a model of $T_{\ah}$. (As you might expect these minimal
extensions are $t$-generic for all $t$.) Second, and quite surpisingly,
$G_{\ah}$ is unique. That is, it does not depend on the ordering of the
witness demands nor on the choice of new points to satisfy them. These
graphs $G_{\ah}$ seem quite intriguing objects worthy of study simply
as countable graphs. For any finite set $X$ of vertices let us define
the closure $cl(X)$ as the union of the $t$-closures of $X$ over all $t$, noting
this is not a first order concept. In this procedure at some finite time all
vertices of $X$ have been touched. Let $Y$ be the value of $cl(X)$
at that moment. After
this time all extensions of $Y$ are via safe extensions and one can show
that $cl(X)$ remains the same. That is, in $G_{\ah}$ all finite sets
have finite closure.
The two models created are different since in the first there is an $x$
with $cl(\{x\})$ infinite while in the second there is no such $x$.
\section{A Dynamic View}
We have seen that for fixed irrational $\ah\in (0,1)$ any first order $A$
holds almost surely or almost never in $G(n,n^{-\ah})$. Now we consider
$A$ fixed and vary $\ah$ - thinking roughly of the evolution of the random
graph as we consider $p=n^{-\ah}$ with $\ah$ decreasing from one to zero.
To study that evolution we define
\[ f_A(\ah) = \lnai \Pr[G(n,n^{-\ah})\models A] \]
To avoid the problems at rational $\ah$ we simply define the domain
of $f_A$ to be the irrational $\ah\in (0,1)$. Our goal is to describe
the possible functions $f_A$.
Note that $f_A(\ah)=1$
when $A$ is in the theory $T_{\ah}$, otherwise $f_A(\ah)=0$. We
have given an explicit description of the theories $T_{\ah}$. In this
sense the function $f_A$ is described independently of probabilistic
calculation. We seek to understand the relationships between the
continuum of theories $T_{\ah}$.
We begin with a continuity result. Fix $A$ and irrational $\ah$. We
claim that $f_A(\beta)$ is constant in some interval $(\ah-\eps,\ah+\eps)$
around $\ah$. Suppose $A$ is in $T_{\ah}$ (otherwise take $\neg A$).
Then $A$ follows from a finite number of axioms of $T_{\ah}$. These
in turn depend on notions of dense and sparse rooted graphs which depend
on whether $v-e\ah$ is positive or negative. For any particular $v,e$
whatever the sign of $v-e\ah$ that sign remains constant in some interval
around $\ah$. The finite number of axioms leads to a finite number of
pairs $v,e$ and so all signs remain constant in some interval. For $\beta$
in that interval $T_{\beta}$ has these same axioms and so $A$ is in $T_{\beta}$.
(It is known, however, that the theories $T_{\ah}$ are all different. Between
any two $\ah,\ah'$ lies a rational $a/b$ and it is known that there is a graph
$H$ such that the existence of a copy of $H$ has threshold function $n^{-a/b}$.)
The discontinuities of $f_A$ must therefore come at the rational
$a/b\in (0,1)$. We define the spectrum $Sp(A)$ to be those rational
points of discontinuity. The classical theory of Random Graphs gives
natural examples. Existence of a $K_4$ has spectrum $\{2/3\}$.
Existence of a $K_5$ has spectrum $\{1/2\}$. We can put these together:
``There exists a $K_4$ and there does not exist a $K_5$" to give
spectrum $\{2/3,1/2\}$ - here as $G$ evolves $\Pr[A]$ starts near zero,
jumps to one at $n^{-2/3}$ when $K_4$ appear and back down to zero
at $n^{-1/2}$ when $K_5$ appear. With some technical work it is not difficult
to get any finite set of rationals in $(0,1)$ as a spectrum in this way.
This author once conjectured that all spectra were such finite sets.
That proved not to be the case.
\section{Infinite Spectra via Almost Sure Encoding}\label{sec-inf}
Here we will describe a first order $A$ with an infinite spectrum. The
central idea will be to take a second order sentence and give it an
almost sure encoding in the first order language.
For definiteness we will work near $\ah=\frac{1}{3}$. By a $K_{3,k}$ is
meant a set $x_1,x_2,x_3;y_1,\ldots,y_k$ with all $y_j$ adjacent to
all three $x$s. Basic random graph theory gives that the sentence
``There exists a $K_{3,k}$" has threshold function $n^{-1/3-1/k}$.
(There are $e=3k$ edges and $v=3+k$ vertices and $(\emptyset,K_{3,k})$
is sparse and safe if and only if $v-e\ah >0$.) Let $N(x_1,x_2,x_3)$ denote
the set of common neighbors of $x_1,x_2,x_3$. Then for
$\frac{1}{3}+\frac{1}{k}> \ah >\frac{1}{3}+\frac{1}{k+1}$ the maximal
size $|N(x_1,x_2,x_3)|$ is $k$. Consider then the property, call it
$A^*$, that the
maximal size $|N(x_1,x_2,x_3)|$ is even. This would have all values
$\frac{1}{3}+\frac{1}{k}$ as spectral points. It is not possible to
write this property in the first order language. We shall, however, give
an almost sure encoding, a first order sentence that almost surely has
the same truth value as $A^*$.
Lets look in the second order world. How can we say that a set $S$
(which will be $N(x_1,x_2,x_3)$ in our application) has even size.
We write:
\[ EVEN(S): \exists_R \forall_x \neg R(x,x) \wedge \forall_{x,y} R(x,y)
\leftrightarrow R(y,x) \wedge \forall_{x\in S}\exists !_{y\in S} R(x,y) \]
That is, there exists an areflexive symmetric binary relation on $S$
(i.\ e.\ a graph) which is a matching - each vertex has precisely one
neighbor. How can we say that $S$ is bigger (or equal) in size to $T$.
Similarly we write $BIGGER(S,T)$ that there exists an areflexive
symmetric binary relation $R$ that yields an injection from $T-S$ to
$S-T$. For every $y\in T-S$ there is a $x\in S-T$ with $R(y,x)$ and we
do not have $R(y_1,x)$ and $R(y_2,x)$ for distinct $y_1,y_2\in T-S$ and
$x\in S-T$. Now we can write $A^*$ in second order:
\[ A^*: \exists_{x_1,x_2,x_3} EVEN[N(x_1,x_2,x_3)]\wedge \]
\[ \wedge \forall_{z_1,z_2,z_3}
BIGGER[N(x_1,x_2,x_3),N(z_1,z_2,z_3)] \]
Now for the almost sure encoding. Define the first order ternary
predicate (considering $u$ as a variable symbol)
\[ R_u(x,y):= \exists_v [v\sim x \wedge v\sim y \wedge v\sim u], \]
that $u,x,y$ have a common neighbor. Our basic (though it will need
modification) idea is to replace the second order $\exists_R $ with
the first order $\exists_u$ and then to replace all instances of the
binary $R$ with the now binary $R_u$.
{\bf Representation Lemma:} For any $s$ and any symmetric
areflexive $R$ on $1,\ldots,s$ that holds for $l$ pairs with $l<\frac{k}{3}$
\[ \forall_{x_1,\ldots,x_s}\exists_u \bigwedge_{1\leq i