{
  "id": "1510.07312",
  "version": "v1",
  "published": "2015-10-25T21:50:56.000Z",
  "updated": "2015-10-25T21:50:56.000Z",
  "title": "Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations",
  "authors": [
    "Josefran de Oliveira Bastos",
    "Leonardo Nagami Coregliano"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "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).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-10-25T21:50:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05D99"
    ],
    "keywords": [
      "monotone sequences",
      "minimum number",
      "packing density",
      "permutation patterns",
      "research paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}