Skip to Main content Skip to Navigation
Conference papers

Decomposable graphs and definitions with no quantifier alternation

Abstract : 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$.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:36 AM
Last modification on : Monday, June 15, 2020 - 12:00:33 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:04:07 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01184380, version 1



Oleg Pikhurko, Joel Spencer, Oleg Verbitsky. Decomposable graphs and definitions with no quantifier alternation. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.25-30. ⟨hal-01184380⟩



Record views


Files downloads