Logic in Computer Science (LICS 1993)

Paper: Infinitary logics and very sparse random graphs (at LICS 1993)

Authors: James F. Lynch

Abstract

The infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas, is considered. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n)<n^-1, then for every σ belonging to the infinitary language the probability that σ holds for the random graph on n vertices converges. Further, if p(n)=n^-a, α>1, then the probability is either smaller than 2 raised to the power-n^d for some d>0, or it is asymptotic to the cn^-d for some c>0, d≥0. Results on the difficulty of computing the asymptotic probability are given

BibTeX

  @InProceedings{Lynch-Infinitarylogicsand,
    author = 	 {James F. Lynch},
    title = 	 {Infinitary logics and very sparse random graphs},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1993},
    year =	 1993,
    editor =	 {Moshe Vardi},
    month =	 {June}, 
    pages =      {191--198},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }