# 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 :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.25-30, 2005, DMTCS Proceedings
Domaine :

Littérature citée [7 références]

https://hal.inria.fr/hal-01184380
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:38:36
Dernière modification le : jeudi 11 mai 2017 - 01:02:53
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:04:07

### Fichier

dmAE0106.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184380, version 1

### Citation

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky. Decomposable graphs and definitions with no quantifier alternation. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.25-30, 2005, DMTCS Proceedings. 〈hal-01184380〉

### Métriques

Consultations de la notice

## 262

Téléchargements de fichiers