On infinite spectra of first order properties of random graphs

2016/09/05 by Maksim Zhukovskii, Zhukovskii, M. E. · 1 citation
Mathematics · #Limits and Structures in Graph Theory #Graph theory and applications #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1609.01115

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

• Spectrum for first-order properties of random hypergraphs

Related

• Spectrum for first-order properties of random hypergraphs
• Bounded quantifier depth spectrum for random uniform hypegraphs
• First order sentences about random graphs: small number of alternations
• On the convergence of probabilities of the random graphs' properties expressed by first-order formulae with a bounded quantifier depth
• Sparse random graphs: Eigenvalues and Eigenvectors