Infinitary logics and very sparse random graphs

Journal of Symbolic Logic 62 (2):609-623 (1997)
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275550
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 27,178
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
Base Rates and Randomness.Ranald R. Macdonald - 1997 - Behavioral and Brain Sciences 20 (4):778-778.
Probability Logic of Finitely Additive Beliefs.Chunlai Zhou - 2010 - Journal of Logic, Language and Information 19 (3):247-282.
Graphical Models, Causal Inference, and Econometric Models.Peter Spirtes - 2005 - Journal of Economic Methodology 12 (1):3-34.
Expansions of Geometries.John T. Baldwin - 2003 - Journal of Symbolic Logic 68 (3):803-827.
Infinitary Logic.John L. Bell - 2008 - Stanford Encyclopedia of Philosophy.
Strong Convergence in Finite Model Theory.Wafik Boulos Lotfallah - 2002 - Journal of Symbolic Logic 67 (3):1083-1092.
Twilight Graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.

Monthly downloads

Added to index

2009-01-28

Total downloads

36 ( #142,008 of 2,163,682 )

Recent downloads (6 months)

1 ( #348,043 of 2,163,682 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums