[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