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

Autor(es)

Bastos, Josefran de Oliveira ^[1] ; Coregliano, Leonardo Nagami ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE; v. 18, n. 2 2016.
• Citações Web of Science: 0

Resumo

In this paper, we present two new results of layered permutation densities. The first one generalizes theorems from Hasto (2003) and Warren (2004) to compute the permutation packing of permutations whose layer sequence is (1(a), l(1), l(2), ... , l(k)) with 2(a)-a-1 >= 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). (AU)

• Processo FAPESP: 13/23720-9 - Combinatória Assintótica de Permutações e Álgebras de Flags
• Beneficiário: Leonardo Nagami Coregliano
• Modalidade de apoio: Bolsas no Brasil - Mestrado