{
  "id": "2009.01086",
  "version": "v1",
  "published": "2020-09-02T14:02:02.000Z",
  "updated": "2020-09-02T14:02:02.000Z",
  "title": "On triangles in derangement graphs",
  "authors": [
    "Andriaherimanana Sarobidy Razafimahatratra",
    "Karen Meagher",
    "Pablo Spiga"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO",
    "math.GR"
  ],
  "abstract": "Given a permutation group $G$, the derangement graph $\\Gamma_G$ of $G$ is the Cayley graph with connection set the set of all derangements of $G$. We prove that, when $G$ is transitive of degree at least $3$, $\\Gamma_G$ contains a triangle. The motivation for this work is the question of how large can be the ratio of the independence number of $\\Gamma_G$ to the size of the stabilizer of a point in $G$. We give examples of transitive groups where this ratio is maximum.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-02T14:02:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "derangement graph",
      "cayley graph",
      "connection set",
      "permutation group",
      "independence number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}