Oleg Pikhurko ; Joel Spencer ; Oleg Verbitsky - Decomposable graphs and definitions with no quantifier alternation

dmtcs:3423 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3423
Decomposable graphs and definitions with no quantifier alternationConference paper

Authors: Oleg Pikhurko ORCID1; Joel Spencer 2; Oleg Verbitsky ORCID3

  • 1 Department of Mathematical Sciences
  • 2 Courant Institute of Mathematical Sciences [New York]
  • 3 Institut fur Informatik

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)2logn+O(1). On the other hand, we prove a lower bound D0(G)lognloglognO(1) for all G. Here logn is equal to the minimum number of iterations of the binary logarithm needed to bring n below 1.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: descriptive complexity of graphs,first order logic,Ehrenfeucht game on graphs,graph decompositions,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Extremal Problems Concerning Forbidden Subgraphs; Funder: National Science Foundation; Code: 0457512

1 Document citing this article

Consultation statistics

This page has been seen 236 times.
This article's PDF has been downloaded 325 times.