DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Decomposable graphs and definitions with no quantifier alternation

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

Abstract


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 D0(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 D0(G)≤2log*n+O(1). On the other hand, we prove a lower bound D0(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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional