[FOM] Zero-one law

[Alasdair Urquhart]

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