On infinite spectra of first order properties of random graphs

Abstract

In this paper, we study spectra of first order properties of Erdos-Renyi random graph. We proved that minimal quantifier depth of a formula with an infinite spectrum is either 4 or 5.

Cited by in corpus (2)

• Spectrum for first-order properties of random hypergraphs
• Combinatorial games on multi-type Galton-Watson trees