Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-15T05:37:05.716Z Has data issue: false hasContentIssue false

Infinitary logics and very sparse random graphs

Published online by Cambridge University Press:  12 March 2014

James F. Lynch*
Affiliation:
Department of Mathematics and Computer Science, Clarkson University, Potsdam, NY 13699-5815, USA, E-mail: jlynch@sun.mcs.clarkson.edu

Abstract

Let 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. It is shown that if p(n) ≪ n−1 satisfies certain simple conditions on its growth rate, then for every , the probability that σ holds for the random graph on n vertices converges. In fact, if p(n) = n−α, α > 1, then the probability is either smaller than for some d > 0, or it is asymptotic to cn−d for some c > 0, d ≥ 0. Results on the difficulty of computing the asymptotic probability are given.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable