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

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

Authors: Josefran de Oliveira Bastos ; Leonardo Nagami Coregliano

    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).


    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)

    Consultation statistics

    This page has been seen 643 times.
    This article's PDF has been downloaded 302 times.