Decomposable graphs and definitions with no quantifier alternation

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

Research output: Contribution to journalArticlepeer-review

Abstract

Let D (G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D0 (G) be the version of D (G) where we do not allow quantifier alternations in Φ. Define q0 (n) to be the minimum of D0 (G) over all graphs G of order n. We prove that for all n we have log* n - log* log* n - 2 ≤ q0 (n) ≤ log* n + 22, where log* n is equal to the minimum number of iterations of the binary logarithm needed to bring n to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.

Original languageEnglish (US)
Pages (from-to)2264-2283
Number of pages20
JournalEuropean Journal of Combinatorics
Volume28
Issue number8
DOIs
StatePublished - Nov 2007

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Decomposable graphs and definitions with no quantifier alternation'. Together they form a unique fingerprint.

Cite this