Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Packing densities of ...
Article

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

Josefran de Oliveira Bastos, Leonardo Nagami Coregliano
Download article
Open on arXiv
Submitted on
June 22, 2016
Published on
June 23, 2016
Last modified on
March 31, 2025
Special issue 18
vol. 18:2, Permutation Patterns 2015
Permutation Patterns
DOI
10.46298/dmtcs.1313
License
arXiv.org - Non-exclusive license to distribute
Indicators
1158
Views
744
Downloads

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

Josefran de Oliveira Bastos, Leonardo Nagami Coregliano
Abstract
In this paper, we present two new results of layered permutation densities. The first one generalizes theorems from H\"{a}st\"{o} (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). Comment: 24 pages
Keywords
  • Mathematics - Combinatorics
  • Computer Science - Discrete Mathematics
  • 05A05 (Primary), 05D99 (Secondary)
Preview
Loading PDF preview...