|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
18 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Monadic second-order properties of very sparse random graphs | | L.B. Ostrovsky
; M.E. Zhukovskii
; | | Date: |
5 Sep 2016 | | Abstract: | We study asymptotical probabilities of first order and monadic second order
properties of Erdos-Renyi random graph G(n,n^{-a}). The random graph obeys FO
(MSO) zero-one k-law if for any first order (monadic second order) formulae it
is true for G(n,n^{-a}) with probability tending to 0 or to 1. Zero-one k-laws
are well studied only for the first order language and a < 1. We obtain new
zero-one k-laws (both for first order and monadic second order languages) when
a > 1. Proofs of these results are based on the existed study of first order
equivalence classes and our study of monadic second order equivalence classes.
The respective results are of interest by themselves. | | Source: | arXiv, 1609.1102 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER