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)

This page has been seen 219 times.

This article's PDF has been downloaded 87 times.