Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. RAN. Ser. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izv. RAN. Ser. Mat., 2017, Volume 81, Issue 6, Pages 100–113 (Mi izv8557)  

This article is cited in 4 scientific papers (total in 4 papers)

First-order properties of bounded quantifier depth of very sparse random graphs

M. E. Zhukovskiiab, L. B. Ostrovskiic

a Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
b Peoples Friendship University of Russia, Moscow
c Company "Yandex"

Abstract: We say that a random graph obeys the zero-one $k$-law if every property expressed by a first-order formula with quantifier depth at most $k$ holds with probability tending to $0$ or $1$. It is known that the random graph $G(n,n^{-\alpha})$ obeys the zero-one $k$-law for every $k\in\mathbb{N}$ and every positive irrational $\alpha$, as well as for all rational $\alpha>1$ which are not of the form $1+1/l$ (for any positive integer $l$). It is also known that for all other rational positive $\alpha$, the random graph does not obey the zero-one $k$-law for sufficiently large $k$. In this paper we put $\alpha=1+1/l$ and obtain upper and lower bounds for the largest $k$ such that the zero-one $k$-law holds.

Keywords: Erdős–Rényi random graph, first-order properties, zero-one law, Ehrenfeucht game.

Funding Agency Grant Number
Russian Foundation for Basic Research 15-01-03530
16-31-60052
Ministry of Education and Science of the Russian Federation 02.A03.21.0008
This paper was written with the financial support of RFBR (grants nos.~15-01-03530 and 16-31-60052) and the Ministry of Science and Education of Russia (Contract no.~02.A03.21.0008).


DOI: https://doi.org/10.4213/im8557

Full text: PDF file (567 kB)
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 2017, 81:6, 1155–1167

Bibliographic databases:

UDC: 519.175.4
MSC: 03B10, 03C13, 05C80, 60F20
Received: 29.03.2016
Revised: 30.10.2016

Citation: M. E. Zhukovskii, L. B. Ostrovskii, “First-order properties of bounded quantifier depth of very sparse random graphs”, Izv. RAN. Ser. Mat., 81:6 (2017), 100–113; Izv. Math., 81:6 (2017), 1155–1167

Citation in format AMSBIB
\Bibitem{ZhuOst17}
\by M.~E.~Zhukovskii, L.~B.~Ostrovskii
\paper First-order properties of bounded quantifier depth of very sparse random graphs
\jour Izv. RAN. Ser. Mat.
\yr 2017
\vol 81
\issue 6
\pages 100--113
\mathnet{http://mi.mathnet.ru/izv8557}
\crossref{https://doi.org/10.4213/im8557}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2017IzMat..81.1155Z}
\elib{https://elibrary.ru/item.asp?id=30737838}
\transl
\jour Izv. Math.
\yr 2017
\vol 81
\issue 6
\pages 1155--1167
\crossref{https://doi.org/10.1070/IM8557}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000418891300005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85040974773}


Linking options:
  • http://mi.mathnet.ru/eng/izv8557
  • https://doi.org/10.4213/im8557
  • http://mi.mathnet.ru/eng/izv/v81/i6/p100

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. M. E. Zhukovskii, S. N. Popova, “A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences”, Dokl. Math., 98:3 (2018), 638–640  mathnet  crossref  crossref  zmath  isi  elib  scopus
    2. A. N. Egorova, M. E. Zhukovskii, “Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph”, Dokl. Math., 99:1 (2019), 68–70  crossref  zmath  isi  scopus
    3. M. E. Zhukovskii, A. S. Razafimahatratra, “Zero-one laws for sentences with $k$ variables”, Dokl. Math., 99:3 (2019), 270–272  crossref  zmath  isi  scopus
    4. A. S. Razafimahatratra, M. Zhukovskii, “Zero-one laws for k-variable first-order logic of sparse random graphs”, Discret Appl. Math., 276:SI (2020), 121–128  crossref  mathscinet  zmath  isi
  • Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya Izvestiya: Mathematics
    Number of views:
    This page:272
    Full text:11
    References:25
    First page:22

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021