Logic in Computer Science (LICS 1995)

Paper: The Infinitary Logic of Sparse Random Graphs (at LICS 1995)

Authors: James F. Lynch Jerzy Tyszkiewicz

Abstract

Let L be 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. Let p(n) be the edge probability of the random graph on n vertices. Previous articles have shown that when p(n) is constant or p(n) is n raised to the power -a and a is greater than 1, then every sentence in L has probability that converges as n gets large; however, when a is less than 1 and is rational, then there are first-order sentences whose probability does not converge. This article completes the picture for L and random graphs with edge probability of the form described above. It is shown that if a is irrational, then every sentence in L has probability that converges to 0 or 1. It is also shown that if a = 1, then there are sentences in the deterministic transitive closure logic (and therefore in L), whose probability does not converge.

BibTeX

  @InProceedings{LynchTyszkiewicz-TheInfinitaryLogico,
    author = 	 {James F. Lynch and Jerzy Tyszkiewicz},
    title = 	 {The Infinitary Logic of Sparse Random Graphs},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {46-53},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }