Let D (G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D0 (G) be the version of D (G) where we do not allow quantifier alternations in Φ. Define q0 (n) to be the minimum of D0 (G) over all graphs G of order n. We prove that for all n we have log* n - log* log* n - 2 ≤ q0 (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.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics