Izvestiya: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
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


Izvestiya: Mathematics, 2017, Volume 81, Issue 6, Pages 1155–1167
DOI: https://doi.org/10.1070/IM8557
(Mi im8557)
 

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"
References:
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).
Received: 29.03.2016
Revised: 30.10.2016
Russian version:
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 2017, Volume 81, Issue 6, Pages 100–113
DOI: https://doi.org/10.4213/im8557
Bibliographic databases:
Document Type: Article
UDC: 519.175.4
Language: English
Original paper language: Russian
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/im8557}
\crossref{https://doi.org/10.4213/im8557}
\adsnasa{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000418891300005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85040974773}
Linking options:
  • https://www.mathnet.ru/eng/im8557
  • https://doi.org/10.1070/IM8557
  • https://www.mathnet.ru/eng/im/v81/i6/p100
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Statistics & downloads:
    Abstract page:440
    Russian version PDF:54
    English version PDF:15
    References:49
    First page:22
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024