Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations

Josefran de Oliveira Bastos, Leonardo Nagami Coregliano

Published 2015-10-25Version 1

In this paper, we present two new results of layered permutation densities. The first one generalizes theorems from H\"ast\"o [P. A. Hasto, The packing density of other layered permutations, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 1, 16, Permutation patterns (Otago, 2003)] and Warren [D. Warren, Optimal packing behavior of some 2-block patterns, Ann. Comb. 8 (2004), no. 3, 355-367] to compute the permutation packing of permutations with layer sequence $(1^a,\ell_1,\ell_2,\ldots,\ell_k)$ such that $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 [J. S. Myers, The minimum number of monotone subsequences, Electron. J. Combin. 9 (2002/03), no. 2, Research paper 4, 17 pp. (electronic), Permutation patterns (Otago, 2003)] for the problem without the layered restriction (the same problem where the monotone sequences have different lengths is also studied).