Bastos, Josefran de Oliveira and Coregliano, Leonardo Nagami - Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations

dmtcs:1516 - Discrete Mathematics & Theoretical Computer Science, June 23, 2016, Vol. 18 no. 2, Permutation Patterns 2015
Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations

Authors: Bastos, Josefran de Oliveira and Coregliano, Leonardo Nagami

In this paper, we present two new results of layered permutation densities. The first one generalizes theorems from H\"{a}stö (2003) and Warren (2004) to compute the permutation packing of permutations whose layer sequence is~$(1^a,\ell_1,\ell_2,\ldots,\ell_k)$ with~$2^a-a-1\geq k$ (and similar permutations). As a second result, we prove that the minimum density of monotone sequences of length~$k+1$ in an arbitrarily large layered permutation is asymptotically~$1/k^k$. This value is compatible with a conjecture from Myers (2003) for the problem without the layered restriction (the same problem where the monotone sequences have different lengths is also studied).


Source : oai:arXiv.org:1510.07312
Volume: Vol. 18 no. 2, Permutation Patterns 2015
Section: Permutation Patterns
Published on: June 23, 2016
Submitted on: June 22, 2016
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05A05 (Primary), 05D99 (Secondary)


Share

Browsing statistics

This page has been seen 166 times.
This article's PDF has been downloaded 67 times.