Upper bound for the minimal quantifier depth of the first part of a monadic second-order sentence without asymptotic probability

2018/02/07 by Sánchez, Mickel González, Zhukovskii, Maksim Evgenievich
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1802.02671

Abstract

In this paper we found an upper bound for the minimal quantifier depth of the first part of a monadic second-order sentence without asymptotic probability described by Jerzy Tyszkiewicz, which express the extension grid axiom in the Erdős-Rényi model of random graphs G(n,n^-α) for some irrational α.

Related

• Short monadic second order sentences about sparse random graphs
• Definitions with no quantifier alternation
• First order sentences about random graphs: small number of alternations
• Zero-one laws for existential first order sentences of bounded quantifier depth
• Logical laws for short existential monadic second order sentences about\n graphs