## 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} }