[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.

http://homepages.math.uic.edu/~jbaldwin/model11.html



Laskowski's

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

http://www2.math.umd.edu/~laskow/

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