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é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 https://doi.org/10.1016/0097-3165%2889%2990022-8
- B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI https://doi.org/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. Appl. Math., New York, 1973) Amer. Math. Soc., Providence, R.I., 1974, pp. 43–73. SIAM-AMS Proc., Vol. VII. MR 0371622
- Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0097-3165%2890%2990061-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 https://doi.org/10.1090/S0894-0347-1988-0924703-8
Retrieve articles in Journal of the American Mathematical Society with MSC: 05C80, 03C13, 60F20
Retrieve articles in all journals with MSC: 05C80, 03C13, 60F20
Additional Information
Article copyright:
© Copyright 1991
American Mathematical Society