Logic in Computer Science (LICS 1996)

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 Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {360-369},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }