Decomposable graphs and definitions with no quantifier alternation |
| |
| Authors: | Oleg Pikhurko Joel Spencer Oleg Verbitsky |
| |
| Institution: | aDepartment of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA;bCourant Institute, New York University, New York, NY 10012, USA;cInstitut für Informatik, Humboldt Universität Berlin, D-10099 Berlin, Germany |
| |
| 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.
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
