{
  "id": "0902.0727",
  "version": "v2",
  "published": "2009-02-04T14:02:18.000Z",
  "updated": "2010-01-14T15:49:40.000Z",
  "title": "On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions",
  "authors": [
    "Filippo Cesi"
  ],
  "comment": "29 pages. Includes modification which appear on the published version in J. Algebraic Combin",
  "journal": "J. Algebraic Combin. 32, no. 2, 155-185 (2010)",
  "doi": "10.1007/s10801-009-0208-x",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a finite simple graph $\\cG$ with $n$ vertices, we can construct the Cayley graph on the symmetric group $S_n$ generated by the edges of $\\cG$, interpreted as transpositions. We show that, if $\\cG$ is complete multipartite, the eigenvalues of the Laplacian of $\\Cay(\\cG)$ have a simple expression in terms of the irreducible characters of transpositions, and of the Littlewood-Richardson coefficients. As a consequence we can prove that the Laplacians of $\\cG$ and of $\\Cay(\\cG)$ have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous's conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-01-14T15:49:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C25",
      "05C50",
      "60K35"
    ],
    "keywords": [
      "complete multipartite set",
      "cayley graph",
      "symmetric group",
      "transpositions",
      "finite simple graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0902.0727C"
    }
  }
}