|
Zero-one laws for random graphs with vertices in a Boolean cube
S. N. Popova Lomonosov Moscow State University, Moscow, Russia
Abstract:
We study the limit probabilities of first-order properties for random graphs with vertices in a Boolean cube. We find sufficient conditions for a sequence of random graphs to obey the zero-one law for first-order formulas of bounded quantifier depth. We also find conditions implying a weakened version of the zero-one law.
Key words:
random graphs, zero-one laws, distance graphs.
DOI:
https://doi.org/10.17377/mattrudy.2016.19.105
Full text:
PDF file (575 kB)
References:
PDF file
HTML file
English version:
Siberian Advances in Mathematics, 2017, 27:1, 26–75
Bibliographic databases:
UDC:
519.175.4 Received: 17.11.2014
Citation:
S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Mat. Tr., 19:1 (2016), 106–177; Siberian Adv. Math., 27:1 (2017), 26–75
Citation in format AMSBIB
\Bibitem{Pop16}
\by S.~N.~Popova
\paper Zero-one laws for random graphs with vertices in a Boolean cube
\jour Mat. Tr.
\yr 2016
\vol 19
\issue 1
\pages 106--177
\mathnet{http://mi.mathnet.ru/mt302}
\crossref{https://doi.org/10.17377/mattrudy.2016.19.105}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3588301}
\elib{https://elibrary.ru/item.asp?id=25963587}
\transl
\jour Siberian Adv. Math.
\yr 2017
\vol 27
\issue 1
\pages 26--75
\crossref{https://doi.org/10.3103/S1055134417010035}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014057607}
Linking options:
http://mi.mathnet.ru/eng/mt302 http://mi.mathnet.ru/eng/mt/v19/i1/p106
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Number of views: |
This page: | 176 | Full text: | 66 | References: | 17 | First page: | 3 |
|