[FOM] Zero-one law
Alasdair Urquhart
urquhart at cs.toronto.edu
Sat Dec 3 10:43:40 EST 2011
The basic reason, I believe, is that whether or
not a 0-1 law holds depends on the appearance
of fixed subgraphs. The details are to
be found in Joel Spencer's fine little book
"The Strange Logic of Random Graphs."
In Chapter 7 of his monograph, Spencer gives
an axiom system T_alpha for an irrational alpha.
This has two schemata -- the NonExistence
Schema and the Generic Extension Schema.
The first says that no copy of a particular
subgraph H satisfying a certain condition
on the ratio of edges to vertices appears.
The proof of the 0-1 law is at the beginning
of Chapter 9. The proof involves showing
that the axioms of the theory T_alpha hold
almost surely for sufficiently large n.
The key point is that an instance of the NonExistence
Schema has a threshold function that
is a negative rational power of n.
In the same way, what prevents a 0-1 law
for rational alpha is the existence of
particular subgraphs. This is explained
in Chapter 8 of Spencer's monograph.
Spencer remarks: "for any
rational number in (0,1), there exists
a strictly balanced graph with that number
as its ratio of vertices to edges"
(Spencer, p. 118).
I recommend Spencer's book highly as a very
pleasant blend of logic and probabilistic
graph theory.
On Fri, 2 Dec 2011, pax0 at seznam.cz wrote:
> 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
More information about the FOM
mailing list