Sh:382
- Shelah, S., & Spencer, J. H. (1994). Can you feel the double jump? Random Structures Algorithms, 5(1), 191–204. arXiv: math/9401211 DOI: 10.1002/rsa.3240050118 MR: 1248186
-
Abstract:
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. - Version 1995-12-08_10 (15p) published version (14p)
Bib entry
@article{Sh:382,
author = {Shelah, Saharon and Spencer, Joel H.},
title = {{Can you feel the double jump?}},
booktitle = {{Proceedings of the Fifth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science (Pozna\'n, 1991)}},
journal = {Random Structures Algorithms},
fjournal = {Random Structures \& Algorithms},
volume = {5},
number = {1},
year = {1994},
pages = {191--204},
issn = {1042-9832},
mrnumber = {1248186},
mrclass = {03C85 (03C13 03D35 05C80 68R10)},
doi = {10.1002/rsa.3240050118},
note = {\href{https://arxiv.org/abs/math/9401211}{arXiv: math/9401211}},
arxiv_number = {math/9401211}
}