{
  "id": "math/0507026",
  "version": "v1",
  "published": "2005-07-01T18:38:47.000Z",
  "updated": "2005-07-01T18:38:47.000Z",
  "title": "RSK Insertion for Set Partitions and Diagram Algebras",
  "authors": [
    "Tom Halverson",
    "Tim Lewandowski"
  ],
  "comment": "24 pages",
  "categories": [
    "math.CO",
    "math.RT"
  ],
  "abstract": "We give combinatorial proofs of two identities from the representation theory of the partition algebra $C A_k(n), n \\ge 2k$. The first is $n^k = \\sum_\\lambda f^\\lambda m_k^\\lambda$, where the sum is over partitions $\\lambda$ of $n$, $f^\\lambda$ is the number of standard tableaux of shape $\\lambda$, and $m_k^\\lambda$ is the number of \"vacillating tableaux\" of shape $\\lambda$ and length $2k$. Our proof uses a combination of Robinson-Schensted-Knuth insertion and jeu de taquin. The second identity is $B(2k) = \\sum_\\lambda (m_k^\\lambda)^2$, where $B(2k)$ is the number of set partitions of $\\{1, >..., 2k\\}$. We show that this insertion restricts to work for the diagram algebras which appear as subalgebras of the partition algebra: the Brauer, Temperley-Lieb, planar partition, rook monoid, planar rook monoid, and symmetric group algebras.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-07-01T18:38:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E10"
    ],
    "keywords": [
      "set partitions",
      "diagram algebras",
      "rsk insertion",
      "partition algebra",
      "symmetric group algebras"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......7026H"
    }
  }
}