When does the zero-one law hold?
HTML articles powered by AMS MathViewer
- by Tomasz Łuczak and Joel Spencer
- J. Amer. Math. Soc. 4 (1991), 451-468
- DOI: https://doi.org/10.1090/S0894-0347-1991-1102581-4
- PDF | Request permission
References
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- Ravi Boppona and Joel Spencer, A useful elementary correlation inequality, J. Combin. Theory Ser. A 50 (1989), no. 2, 305–307. MR 989201, DOI 10.1016/0097-3165(89)90022-8
- B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI 10.1007/BF02579198
- 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 125031
- Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Proc. SIAM-AMS Sympos., New York, 1973) SIAM-AMS Proc., Vol. VII, Amer. Math. Soc., Providence, R.I., 1974, pp. 43–73. MR 0371622
- Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI 10.2307/2272945 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. 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).
- Joel Spencer, Countable sparse random graphs, Random Structures Algorithms 1 (1990), no. 2, 205–214. MR 1138426, DOI 10.1002/rsa.3240010207
- Joel Spencer, Threshold functions for extension statements, J. Combin. Theory Ser. A 53 (1990), no. 2, 286–305. MR 1041449, DOI 10.1016/0097-3165(90)90061-Z
- Saharon Shelah and Joel Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), no. 1, 97–115. MR 924703, DOI 10.1090/S0894-0347-1988-0924703-8
Bibliographic Information
- © Copyright 1991 American Mathematical Society
- 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