Can I read Definitions with No Quantifier Alternation on EtoBox?

Definitions with No Quantifier Alternation by Pikhurko, Oleg; Spencer, Joel; Verbitsky, Oleg is a scholarly article available to read on EtoBox.

What is Definitions with No Quantifier Alternation about?

Let $D(G)$ be the minimum quantifier depth of a first order sentence $\Phi$ that defines a graph $G$ up to isomorphism. Let $D_0(G)$ be the version of $D(G)$ where we do not allow quantifier alternations in $\Phi$. Define $q_0(n)$ to be the minimum of $D_0(G)$ over all graphs $G$ of order $n$. We prove that for all $n$ we have $\log^*n-\log^*\log^*n-1\le q_0(n)\le \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.

Author

Pikhurko, Oleg; Spencer, Joel; Verbitsky, Oleg

Published

2004

Language

EN