[hal-01184380] Decomposable graphs and definitions with no quantifier alternation

Let D(G) be the minimum quantifier depth of a first order sentence Φ 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 Φ . 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)≤ 2\log ^*n+O(1). On the other hand, we prove a lower bound D_0(G)≥ \log ^*n-\log ^*\log ^*n-O(1) for all G. Here \log ^*n is equal to the minimum number of iterations of the binary logarithm needed to bring n below 1.

from HAL : Dernières publications http://ift.tt/1UISdC1