On the logical complexity of convex polygon dissections

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The logical depth of a graph $G$ is the minimum quantifier depth of a first order sentence defining $G$ up to isomorphism in the language of the adjacency and the equality relations. We consider the case that $G$ is a dissection of a convex polygon or, equivalently, a biconnected outerplanar graph. We bound the logical depth of a such $G$ from above by a function of combinatorial parameters of the dual tree of $G$.
26 pages

Keywords

Combinatorics, Logic

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/115070

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0607531
 http://arxiv.org/abs/math/0607531

Collections

arXiv