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.
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).
Citation:
M. E. Zhukovskii, L. B. Ostrovskii, “First-order properties of bounded quantifier depth of very sparse random graphs”, Izv. Math., 81:6 (2017), 1155–1167
\Bibitem{ZhuOst17}
\by M.~E.~Zhukovskii, L.~B.~Ostrovskii
\paper First-order properties of bounded quantifier depth of very sparse random graphs
\jour Izv. Math.
\yr 2017
\vol 81
\issue 6
\pages 1155--1167
\mathnet{http://mi.mathnet.ru/eng/im8557}
\crossref{https://doi.org/10.1070/IM8557}
\zmath{https://zbmath.org/?q=an:1406.03050}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2017IzMat..81.1155Z}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000418891300005}
\elib{https://elibrary.ru/item.asp?id=30737838}
\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:
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
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
M. E. Zhukovskii, A. S. Razafimahatratra, “Zero-one laws for sentences with $k$ variables”, Dokl. Math., 99:3 (2019), 270–272
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