Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

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

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [B] B. Bollobás, Random graphs, Academic Press, New York, 1985. MR 809996 (87f:05152)
  • [BS] R. Boppana and J. Spencer, A useful elementary correlation inequality, J. Combin. Theory Ser. A 50 (1989), 305-307. MR 989201 (90e:60011)
  • [BT] B. Bollobás and A.G. Thomason, Threshold functions, Combinatorica 7 (1986), 35-38. MR 905149 (88g:05122)
  • [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. MR 0125031 (23:A2338)
  • [F1] R. Fagin, Generalized first order spectra and polynomial time recognizable sets, Complexity of Computation (SIAM-AMS Proc., New York, April 18-19, 1973), vol. 7 (R. M. Karp, ed.), 1974, pp. 43-73. MR 0371622 (51:7840)
  • [F2] -, Probabilities on finite models, J. Symbolic Logic 41 (1976), 50-58. MR 0476480 (57:16042)
  • [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] J. Spencer, Countable sparse random graphs, Random Structures and Algorithms 1 (1990), 205-214. MR 1138426 (92m:05176)
  • [S2] -, Threshold functions for extension statements, J. Combin. Theory Ser. A 53 (1990), 286-305. MR 1041449 (91c:05168)
  • [SS] J. Spencer and S. Shelah, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), 97-115. MR 924703 (89i:05249)

Similar Articles

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

DOI: https://doi.org/10.1090/S0894-0347-1991-1102581-4
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society