DocumentCode
2785128
Title
Probabilities of sentences about very sparse random graphs
Author
Lynch, James F.
Author_Institution
Dept. of Math. & Comput. Sci., Clarkson Univ., Potsdam, NY, USA
fYear
1990
fDate
22-24 Oct 1990
Firstpage
689
Abstract
The author considers 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 . It is proved that, for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit. Also, there is an effective procedure for generating the value of the limit in closed form
Keywords
formal languages; graph theory; edge probability; first-order sentence; fixed positive integer; very sparse random graphs; Application software; Combinatorial mathematics; Computer science; Formal languages; Logic; Probability distribution;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location
St. Louis, MO
Print_ISBN
0-8186-2082-X
Type
conf
DOI
10.1109/FSCS.1990.89591
Filename
89591
Link To Document