Probabilities of Sentences about Very Sparse Random Graphs
- 1 January 1992
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 3 (1) , 33-53
- https://doi.org/10.1002/rsa.3240030105
Abstract
We consider random graphs with edge probability βn−α, where n is the number of vertices of the graph, β > 0 is fixed, and α = 1 or α = (l + 1) /l for some fixed positive integer l. We prove that for every first‐order sentence, the probability that the sentence is true for the random graph has an asymptotic limit.Keywords
This publication has 16 references indexed in Scilit:
- Threshold spectra via the Ehrenfeucht gameDiscrete Applied Mathematics, 1991
- A uniform method for proving lower bounds on the computational complexity of logical theoriesAnnals of Pure and Applied Logic, 1990
- A logical approach to asymptotic combinatorics II: Monadic second-order propertiesJournal of Combinatorial Theory, Series A, 1989
- Nonconvergence, undecidability, and intractability in asymptotic problemsAnnals of Pure and Applied Logic, 1987
- Probabilities of first-order sentences about unary functionsTransactions of the American Mathematical Society, 1985
- Probabilities of First-Order Sentences about Unary FunctionsTransactions of the American Mathematical Society, 1985
- Complexity of the first-order theory of almost all finite structuresInformation and Control, 1983
- Almost sure theoriesAnnals of Mathematical Logic, 1980
- Probabilities on finite modelsThe Journal of Symbolic Logic, 1976
- Range and degree of realizability of formulas in the restricted predicate calculusCybernetics and Systems Analysis, 1972