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 2 scientific papers (total in 2 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)
First page: PDF file
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{http://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{http://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
    2. Egorova A.N., Zhukovskii M.E., “Disproof of the Zero-One Law For Existential Monadic Properties of a Sparse Binomial Random Graph”, Dokl. Math., 99:1 (2019), 68–70  crossref  isi
  • Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya Izvestiya: Mathematics
    Number of views:
    This page:209
    References:20
    First page:20

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019