Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Dokl. RAN. Math. Inf. Proc. Upr.:
Year:
Volume:
Issue:
Page:
Find




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

Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia, 2021, Volume 500, Pages 31–34
DOI: https://doi.org/10.31857/S2686954321050180 (Mi danma200) 		 
MATHEMATICS

On the 4-spectrum of first-order properties of random graphs

M. E. Zhukovskiiabcd, A. D. Matushkina, Yu. N. Yarovikovae

a Moscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Moscow oblast, Russia
b Russian Academy of National Economy and Public Administration under the President of the Russian Federation, Moscow, Russia
c Caucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea, Russia
d Moscow Center for Fundamental and Applied Mathematics, Moscow, Russia
e Artificial Intelligence Research Institute, Moscow, Russia
Full-text PDF (105 kB)
References:
PDF
HTML
DOI: https://doi.org/10.31857/S2686954321050180
Abstract: A $k$-spectrum is a set of all positive $\alpha$ such that the random binomial graph $G(n,n^{-\alpha})$ does not obey the zero–one law for first-order formulas with a quantifier depth at most $k$. We have proved that the minimal $k$ such that the $k$-spectrum is infinite equals 5.
Keywords: first-order logic, random binomial graph, zero–one law, spectrum of formula, Ehrenfeucht–Fraïssé game.
Funding agency Grant number
Russian Foundation for Basic Research 20-31-70025
This work was supported by the Russian Foundation for Basic Research, project no. 20-31-70025.
Presented: V. V. Kozlov
Received: 27.04.2021
Revised: 07.07.2021
Accepted: 18.08.2021
English version:
Doklady Mathematics, 2021, Volume 104, Issue 2, Pages 247–249
DOI: https://doi.org/10.1134/S1064562421050185
Bibliographic databases:
Document Type: Article
UDC: 519.175.4
Language: Russian
Citation: M. E. Zhukovskii, A. D. Matushkin, Yu. N. Yarovikov, “On the 4-spectrum of first-order properties of random graphs”, Dokl. RAN. Math. Inf. Proc. Upr., 500 (2021), 31–34; Dokl. Math., 104:2 (2021), 247–249
Citation in format AMSBIB
\Bibitem{ZhuMatYar21}
\by M.~E.~Zhukovskii, A.~D.~Matushkin, Yu.~N.~Yarovikov
\paper On the 4-spectrum of first-order properties of random graphs
\jour Dokl. RAN. Math. Inf. Proc. Upr.
\yr 2021
\vol 500
\pages 31--34
\mathnet{http://mi.mathnet.ru/danma200}
\crossref{https://doi.org/10.31857/S2686954321050180}
\zmath{https://zbmath.org/?q=an:7492938}
\elib{https://elibrary.ru/item.asp?id=47249626}
\transl
\jour Dokl. Math.
\yr 2021
\vol 104
\issue 2
\pages 247--249
\crossref{https://doi.org/10.1134/S1064562421050185}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85124354392}
Linking options:
  • https://www.mathnet.ru/eng/danma200
  • https://www.mathnet.ru/eng/danma/v500/p31
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025