[FOM] Zero-one law

John Baldwin jbaldwin at uic.edu
Sat Dec 3 09:16:02 EST 2011

> This has been proved:
>> Fixing an irrational alpha in (0, 1) we prove the 0-1 law for the random
>> graph on [n] with the probability of {i, j} being an edge being essentially
>> |i−j|^-alpha
> Can someone explain how the irrationality of alpha is used in this claim?
> Thank you, Jan Pax

There is a long history of this subject beginning with Spencer-Shelah.
One way is which the role of the irrationality is seen in the model 
theoretic approach of Baldwin-Shelah. Here the crucial point is that the 
Hrushovski dimension function delta(B/A) for the relative dimension of a 
graph B and a graph A is given by number of (vertices in B-A) - 
alpha(number of new edges introduced) is never 0 if alpha is irrational.

Also Spencer-Shelah show the zero-one law fails for rational alpha.  (edge 
probability n^{-alpha}).

Pax actually refers to a slightly different wrinkle where the probability 
depends on the distance  between vertices rather than the size of 
the graph. I know only that Shelah has work in this direction.

There are a number of relevant papers on my webpage.  The metamathematics 
of random 
graphs (2005) gives a little history.



A simpler axiomatization of the Shelah-Spencer almost sure theories, 
Israel Journal of Mathematics 161(2007), 157-186.   .pdf


is the most modern and simple version.

> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> !DSPAM:4ed9c3e0111414824652309!

More information about the FOM mailing list