Infinitary Logics and Very Sparse Random Graphs
Lynch, James F.
J. Symbolic Logic, Tome 62 (1997) no. 1, p. 609-623 / Harvested from Project Euclid
Let $L^\omega_{\infty\omega}$ 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) \ll n^{-1}$ satisfies certain simple conditions on its growth rate, then for every $\sigma\in L^\omega_{\infty\omega}$, the probability that $\sigma$ holds for the random graph on $n$ vertices converges. In fact, if $p(n) = n^{-\alpha}, \alpha > 1$, then the probability is either smaller than $2^{-n^d}$ for some $d > 0$, or it is asymptotic to $cn^{-d}$ for some $c > 0, d \geq 0$. Results on the difficulty of computing the asymptotic probability are given.
Publié le : 1997-06-14
Classification: 
@article{1183745246,
     author = {Lynch, James F.},
     title = {Infinitary Logics and Very Sparse Random Graphs},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 609-623},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745246}
}
Lynch, James F. Infinitary Logics and Very Sparse Random Graphs. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  609-623. http://gdmltest.u-ga.fr/item/1183745246/