In this paper, we present two new results of layered permutation densities. The first one generalizes theorems from Hä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 293 times.

This article's PDF has been downloaded 128 times.