Universität zu Köln

Disanto, Filippo and Wiehe, Thomas ORCID: 0000-0002-8932-2772 (2014). On the sub-permutations of pattern avoiding permutations. Discret. Math., 337. S. 127 - 142. AMSTERDAM: ELSEVIER. ISSN 1872-681X

Full text not available from this repository.

Abstract

There is a deep connection between permutations and trees. Certain sub-structures of permutations, called sub-permutations, bijectively map to sub-trees of binary increasing trees. This opens a powerful tool set to study enumerative and probabilistic properties of sub-permutations and to investigate the relationships between 'local' and 'global' features using the concept of pattern avoidance. First, given a pattern mu, we study how the avoidance of mu in a permutation pi affects the presence of other patterns in the sub-permutations of pi. More precisely, considering patterns of length 3, we solve instances of the following problem: given a class of permutations K and a pattern mu, we ask for the number of permutations pi is an element of Av(n)(mu) whose sub-permutations in K satisfy certain additional constraints on their size. Second, we study the probability for a generic pattern to be contained in a random permutation pi of size n without being present in the sub-permutations of pi generated by the entry 1 <= k <= n. These theoretical results can be useful to define efficient randomized pattern-search procedures based on classical algorithms of pattern-recognition, while the general problem of pattern-search is NP-complete. (C) 2014 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Disanto, Filippo UNSPECIFIED UNSPECIFIED UNSPECIFIED Wiehe, Thomas UNSPECIFIED orcid.org/0000-0002-8932-2772 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-419970
DOI:	10.1016/j.disc.2014.06.028
Journal or Publication Title:	Discret. Math.
Volume:	337
Page Range:	S. 127 - 142
Date:	2014
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1872-681X
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Biology > Institute for Genetics
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language TREES Multiple languages Mathematics Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/41997