Can you feel the double jump? (English) Zbl 0789.03015
Summary: When \(p=c/n\) and \(c\) goes from less than one to greater than one, the random graph \(G(n,p)\) experiences the double jump. The first order language is too weak to recognize this change while there are properties expressible in the second order monadic language for which the change is clear.
MSC:
| 03B30 | Foundations of classical theories (including reverse mathematics) |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 03B25 | Decidability of theories and sets of sentences |
| 03B15 | Higher-order logic; type theory (MSC2010) |
References:
| [1] | Random Graphs, Academic Press, London, 1985. |
| [2] | Erdös, Mat. Kutató Int. Közl. 5 pp 17– (1960) |
| [3] | Lynch, Random Struct. Alg. 3 pp 33– (1992) |
| [4] | Rabin, Trans. Am. Math. Soc. 141 pp 1– (1969) |
| [5] | Traktenbrot, Dokl. Akad. Nauk. SSR 70 pp 569– (1950) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
