On the 4-Spectrum of First-Order Properties of Random Graphs

M. E. Zhukovskii^a^,^b^,^c^,^d^,*, A. D. Matushkin^a^,**, and Yu. N. Yarovikov^a^,^e^,***

^a Moscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Moscow oblast, 141701 Russia

^bRussian Presidential Academy of National Economy and Public Administration, Moscow, Russia

^cCaucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea, Russia

^dMoscow Center for Fundamental and Applied Mathematics, Moscow, Russia

^eArtificial Intelligence Research Institute, Moscow, Russia

Correspondence to: *e-mail: zhukmax@gmail.com
Correspondence to: **e-mail: 1alexmatushkin1@gmail.com
Correspondence to: ***e-mail: yu-rovikov@yandex.ru

Received 27 April, 2021

Abstract—A k-spectrum is a set of all positive α 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

DOI: 10.1134/S1064562421050185