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., 2021, Volume 500,Pages <nobr>31

MATHEMATICS

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

M. E. Zhukovskii^abcd, A. D. Matushkin^a, Yu. N. Yarovikov^ae

^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

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ïssé game.

UDC: 519.175.4

Presented: V. V. Kozlov
Received: 27.04.2021
Revised: 07.07.2021
Accepted: 18.08.2021

DOI: 10.31857/S2686954321050180