{
  "id": "math/0609644",
  "version": "v1",
  "published": "2006-09-22T14:48:29.000Z",
  "updated": "2006-09-22T14:48:29.000Z",
  "title": "Shape-Wilf-ordering of permutations of length 3",
  "authors": [
    "Zvezdelina Stankova"
  ],
  "comment": "38 pages, 32 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The research on pattern-avoidance has yielded so far limited knowledge on Wilf-ordering of permutations. The Stanley-Wilf limits sqrt[n](|S_n(tau)|) and further works suggest asymptotic ordering of layered versus monotone patterns. Yet, Bona has provided the only known up to now result of its type on ordering of permutations: |S_n(1342)|<|S_n(1234)|<|S_n(1324)| for n>6. We give a different proof of this result by ordering S_3 up to the stronger shape-Wilf-order: |S_Y(213)|<=|S_Y(123)|<=|S_Y(312)| for any Young diagram Y, derive as a consequence that |S_Y(k+2,k+1,k+3,tau)|<=|S_Y(k+1,k+2,k+3,tau)|<= |S_Y(k+3,k+1,k+2,tau)| for any tau in S_k, and find out when equalities are obtained. (In particular, for specific Y's we find out that |S_Y(123)|=|S_Y(312)| coincide with every other Fibonacci term.) This strengthens and generalizes Bona's result to arbitrary length permutations. While all length-3 permutations have been shown in numerous ways to be Wilf-equivalent, the current paper distinguishes between and orders these permutations by employing all Young diagrams. This opens up the question of whether shape-Wilf-ordering of permutations, or some generalization of it, is not the ``true'' way of approaching pattern-avoidance ordering.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-09-22T14:48:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A20",
      "05A15"
    ],
    "keywords": [
      "young diagram",
      "generalizes bonas result",
      "arbitrary length permutations",
      "current paper distinguishes",
      "specific ys"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......9644S"
    }
  }
}