loading...
The Infinitary Logic of Sparse Random Graphs
San Diego, California June 26-June 29
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.1995.52324310th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
James F. Lynch, Clarkson University
Jerzy Tyszkiewicz, Mathematische Grundlagen der Informatik, Aachen, Germany
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.
Index Terms:
Finite model theory, infinitary logic, random graphs
Citation:
James F. Lynch, Jerzy Tyszkiewicz, "The Infinitary Logic of Sparse Random Graphs," lics, pp.46, 10th Annual IEEE Symposium on Logic in Computer Science (LICS'95), 1995
Usage of this product signifies your acceptance of the Terms of Use.