When does the zero-one law hold?

When does the zero-one law hold?
HTML articles powered by AMS MathViewer

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

Range and degree of realizability of formulas in the restricted predicate calculus

5

An exponential bound for the probability of nonexistence of a specified subgraph in a random graph

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