Katherine St. John

		      Random Bit Strings


The ordered structures with a single unary predicate-- that is, bit
strings-- are a natural class to study both for their beauty as
mathematical structures and their role in computer science.  Much work
has been done linking classes of bit strings and ordered graphs to
complexity classes.  In this talk, we will discuss properties of
random graphs and bit strings, in particular, joint work with Joel
Spencer on sparse random bit strings.

The random bit string, U_{n,p}, is a probability space over unary
predicates U on [n] = {1,...,n} with the probabilities determined by

Pr[U(x)] = p(n), for 0 &lt x &lt n+1,

and the events U(x) are mutually independent over 0 &lt x &lt n+1.  We
are interested in what happens to properties of the random bit string
as the length of the string goes to infinity.  How does this change as
the underlying probability p(n) changes?  Also, what do the models of
the sentences that are almost surely true (e.g. the almost sure
theory) look like?  We will give an overview of this work and discuss
what happens at some interesting probabilities.