Zero-one laws for sparse random graphs

Shelah, Saharon; Spencer, Joel

doi:10.1090/S0894-0347-1988-0924703-8

Zero-one laws for sparse random graphs

Authors: Saharon Shelah and Joel Spencer
Journal: J. Amer. Math. Soc. 1 (1988), 97-115
MSC: Primary 05C80; Secondary 03C13, 03C65
DOI: https://doi.org/10.1090/S0894-0347-1988-0924703-8
MathSciNet review: 924703
Full-text PDF Free Access

References | Similar Articles | Additional Information

[1] Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
[2] B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, https://doi.org/10.1007/BF02579198
[3] Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493–507. MR 57518, https://doi.org/10.1214/aoms/1177729330
[4] P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90. MR 111692, https://doi.org/10.1112/jlms/s1-35.1.85
[5] P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 0125031
[6] Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, https://doi.org/10.2307/2272945
[7] Y. V. Glebskii, D. I. Kogan, M. I. Liogonkii and V. A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics 5, 142-154.
[8] Leo Marcus, Minimal models of theories of one function symbol, Israel J. Math. 18 (1974), 117–131. MR 351798, https://doi.org/10.1007/BF02756866
[9] Matt Kaufmann and Saharon Shelah, On random models of finite power and monadic logic, Discrete Math. 54 (1985), no. 3, 285–293. MR 790589, https://doi.org/10.1016/0012-365X(85)90112-8