Infinitary logics and very sparse random graphs

Journal of Symbolic Logic 62 (2):609-623 (1997)
  Copy   BIBTEX

Abstract

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. It is shown that if p(n) ≪ n -1 satisfies certain simple conditions on its growth rate, then for every σ∈ L ω ∞ω , the probability that σ 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Base rates and randomness.Ranald R. Macdonald - 1997 - Behavioral and Brain Sciences 20 (4):778-778.
Twilight graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.
Strong convergence in finite model theory.Wafik Boulos Lotfallah - 2002 - Journal of Symbolic Logic 67 (3):1083-1092.
Infinitary logic.John L. Bell - 2008 - Stanford Encyclopedia of Philosophy.
Expansions of geometries.John T. Baldwin - 2003 - Journal of Symbolic Logic 68 (3):803-827.
Graphical models, causal inference, and econometric models.Peter Spirtes - 2005 - Journal of Economic Methodology 12 (1):3-34.
Probability logic of finitely additive beliefs.Chunlai Zhou - 2010 - Journal of Logic, Language and Information 19 (3):247-282.

Analytics

Added to PP
2009-01-28

Downloads
68 (#217,472)

6 months
12 (#122,989)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references