# 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. - 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}, doi = {10.1002/rsa.3240050118}, mrclass = {03C85 (03C13 03D35 05C80 68R10)}, mrnumber = {1248186}, mrreviewer = {S. R. Kogalovski\u{\i}}, doi = {10.1002/rsa.3240050118}, note = {\href{https://arxiv.org/abs/math/9401211}{arXiv: math/9401211}}, arxiv_number = {math/9401211} }