Definitions with no quantifier alternation

2004/05/17 by Pikhurko, Oleg, Spencer, Joel, Verbitsky, Oleg
#03C13 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.math/0405326

Abstract

Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D₀(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q₀(n) to be the minimum of D₀(G) over all graphs G of order n. We prove that for all n we have log^*n-log^*log^*n-1≤ q₀(n)≤ log^*n+22, where log^*n is equal to the minimum number of iterations of the binary logarithm needed to bring n to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.

Related

• Succinct Definitions in the First Order Theory of Graphs
• Upper bound for the minimal quantifier depth of the first part of a monadic second-order sentence without asymptotic probability
• First order sentences about random graphs: small number of alternations
• Logical complexity of graphs: a survey
• Logical complexity of induced subgraph isomorphism for certain graph families