New interface

# 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$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [7 references]

https://hal.inria.fr/hal-01184380
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:38:36 AM
Last modification on : Tuesday, November 22, 2022 - 11:10:08 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:04:07 AM

### File

dmAE0106.pdf
Publisher files allowed on an open archive

### 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, ⟨10.46298/dmtcs.3423⟩. ⟨hal-01184380⟩

Record views