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

https://hal.inria.fr/hal-01184380
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

File

dmAE0106.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184380, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

342

Files downloads

923