Paper: Zero-one laws for Gilbert random graphs (at LICS 1996)

Authors: Gregory L. McColm

Abstract

We look at a competitor of the Erdos-Renyi models of random graphs, one proposed by E. Gilbert (1961): given /spl delta/>0 and a metric space X of diameter >/spl delta/, scatter n vertices at random on X and connect those of distance apart: we get a random graph G/sub n,/spl delta///sup X/. Question: for fixed X, /spl delta/, do we have 0-1 laws for FO logic? We prove that this is true if X is a circle.

BibTeX

  @InProceedings{McColm-ZeroonelawsforGilbe,
    author = 	 {Gregory L. McColm},
    title = 	 {Zero-one laws for Gilbert random graphs},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS 1996)},
    year =	 {1996},
    month =	 {July}, 
    pages =      {360--369},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }