### Can You Feel the Double Jump?

by Shelah and Spencer. [ShSp:382]

Random Structures and Algorithms, 1994

Paul Erdos and Alfred Renyi considered the evolution of the
random graph G(n,p) as p ``evolved'' from 0 to 1 . At p=1/n
a sudden and dramatic change takes place in G . When p=c/n with
c<1 the random G consists of small components, the largest of
size Theta(log n) . But by p=c/n with c>1 many of the
components have ``congealed'' into a ``giant component'' of size
Theta (n) . Erdos and Renyi called this the double jump, the
terms phase transition (from the analogy to percolation) and Big
Bang have also been proferred. Now imagine an observer who can only
see G through a logical fog. He may refer to graph theoretic
properties A within a limited logical language. Will he be able
to detect the double jump? The answer depends on the strength of the
language. Our rough answer to this rough question is: the double
jump is not detectible in the First Order Theory of Graphs but it is
detectible in the Second Order Monadic Theory of Graphs.

Back to the list of publications