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

**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 Symposium on Logic in Computer Science (LICS 1993)}, year = {1993}, month = {June}, pages = {191--198}, location = {Montreal, Canada}, publisher = {IEEE Computer Society Press} }