Decomposable graphs and definitions with no quantifier alternation

Pikhurko, Oleg ; Spencer, Joel ; Verbitsky, Oleg

Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Résumé

Let $D(G)$ be the minimum quantifier depth of a first order sentence $\Phi$ that defines a graph $G$ up to isomorphism in terms of the adjacency and the equality relations. Let $D_0(G)$ be a variant of $D(G)$ where we do not allow quantifier alternations in $\Phi$. Using large graphs decomposable in complement-connected components by a short sequence of serial and parallel decompositions, we show examples of $G$ on $n$ vertices with $D_0(G) \leq 2 \log^{\ast}n+O(1)$. On the other hand, we prove a lower bound $D_0(G) \geq \log^{\ast}n-\log^{\ast}\log^{\ast}n-O(1)$ for all $G$. Here $\log^{\ast}n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ below $1$.

Détail

DOI : 10.46298/dmtcs.3423