When does the zero-one law hold?

Łuczak, Tomasz; Spencer, Joel

doi:10.1090/S0894-0347-1991-1102581-4

When does the zero-one law hold?

Authors: Tomasz Łuczak and Joel Spencer
Journal: J. Amer. Math. Soc. 4 (1991), 451-468
MSC: Primary 05C80; Secondary 03C13, 60F20
DOI: https://doi.org/10.1090/S0894-0347-1991-1102581-4
MathSciNet review: 1102581
Full-text PDF Free Access

References | Similar Articles | Additional Information

[B] Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
[BS] Ravi Boppona and Joel Spencer, A useful elementary correlation inequality, J. Combin. Theory Ser. A 50 (1989), no. 2, 305–307. MR 989201, https://doi.org/10.1016/0097-3165(89)90022-8
[BT] B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, https://doi.org/10.1007/BF02579198
[ER] 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
[F1] Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973) Amer. Math. Soc., Providence, R.I., 1974, pp. 43–73. SIAM-AMS Proc., Vol. VII. MR 0371622
[F2] Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, https://doi.org/10.2307/2272945
[GKLT] Y. V. Glebskii, D. I. Kogan, M. I. Liogonkii, and Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics 5 (1969), 142-154.
[JLR] S. Janson, T. Luczak, and A. Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph (to appear).
[S1] Joel Spencer, Countable sparse random graphs, Random Structures Algorithms 1 (1990), no. 2, 205–214. MR 1138426, https://doi.org/10.1002/rsa.3240010207
[S2] Joel Spencer, Threshold functions for extension statements, J. Combin. Theory Ser. A 53 (1990), no. 2, 286–305. MR 1041449, https://doi.org/10.1016/0097-3165(90)90061-Z
[SS] Saharon Shelah and Joel Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), no. 1, 97–115. MR 924703, https://doi.org/10.1090/S0894-0347-1988-0924703-8