{
  "id": "1306.3611",
  "version": "v2",
  "published": "2013-06-15T22:50:11.000Z",
  "updated": "2014-09-09T11:28:47.000Z",
  "title": "Geodesics in a Graph of Perfect Matchings",
  "authors": [
    "Roy Ben-Ari"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper studies geodesics in the graph $\\mathscr{P}_{m}$, which has all perfect matchings in $K_{2m}$ as vertices with two perfect matchings connected by an edge if their symmetric difference is a cycle of length four. The diameter of $\\mathscr{P}_{m}$, as well as the eccentricity of each vertex, are shown to be $m-1$. The number of geodesics between any two antipodes is shown to be $m^{m-2}$ and an explicit formula for the number of geodesics between any two matchings in $\\mathscr{P}_{m}$ is given. The paper concludes by showing that the subgraph of non-crossing perfect matchings has exactly one pair of antipodes having the maximal number ($m^{m-2}$) of geodesics.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-06-15T22:50:11.000Z",
      "title": "Combinatorial Parameters on Matchings in Complete and Complete Bipartite Graphs",
      "abstract": "Take $2m$ labeled points on a circle and join them in disjoint pairs by $m$ chords. The resulting diagram is called a chord diagram. In our research we study the graph of chord diagrams $\\cm$, a graph that has, as vertices, all chord diagrams, and two diagrams are connected by an edge in the graph if their symmetric difference is a cycle of length four. We show that the diameter as well as the eccentricity of every vertex in $\\cm$ are $m-1$. We prove the following surprising result: The number of shortest paths between every two antipodes is exactly $m^{m-2}$. Note, that the expression $m^{m-2}$ appears in the well known Cayley Formula for the number of labeled trees on $m$ points. We then give an explicit formula for the number of shortest paths between any two diagrams in $\\cm$. We conclude by showing there is exactly one pair of antipodes in the graph of non-crossing diagrams $\\mm$ with $m^{m-2}$ shortest paths between them. All other pairs have a smaller number of shortest paths.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-09-09T11:28:47.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete bipartite graphs",
      "combinatorial parameters",
      "shortest paths",
      "chord diagram",
      "explicit formula"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1306.3611B"
    }
  }
}