Simple permutations: decidability and unavoidable substructures

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We prove that it is decidable if a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length k.

Keywords

Combinatorics

Citation

URI

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

Consulte el texto completo en el siguiente enlace:

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

Collections

arXiv