Title :
Zero-one laws for Gilbert random graphs
Author :
McColm, Gregory L.
Author_Institution :
Dept. of Math., Univ. of South Florida, Tampa, FL, USA
Abstract :
We look at a competitor of the Erdos-Renyi models of random graphs, one proposed by E. Gilbert (1961): given δ>0 and a metric space X of diameter >δ, scatter n vertices at random on X and connect those of distance <δ apart: we get a random graph Gn,δX. Question: for fixed X, δ, do we have 0-1 laws for FO logic? We prove that this is true if X is a circle
Keywords :
computational geometry; graph theory; Erdos-Renyi models; Gilbert random graphs; metric space; vertices; zero-one laws; Biological system modeling; Biological tissues; Chemical processes; Extraterrestrial measurements; Graph theory; Head; Logic; Mathematics; Scattering;
Conference_Titel :
Logic in Computer Science, 1996. LICS '96. Proceedings., Eleventh Annual IEEE Symposium on
Conference_Location :
New Brunswick, NJ
Print_ISBN :
0-8186-7463-6
DOI :
10.1109/LICS.1996.561448
