{
  "id": "1712.03688",
  "version": "v1",
  "published": "2017-12-11T09:28:15.000Z",
  "updated": "2017-12-11T09:28:15.000Z",
  "title": "On the Saxl graph of a permutation group",
  "authors": [
    "Timothy C. Burness",
    "Michael Giudici"
  ],
  "comment": "25 pages",
  "categories": [
    "math.GR",
    "math.CO"
  ],
  "abstract": "Let $G$ be a permutation group on a set $\\Omega$. A subset of $\\Omega$ is a base for $G$ if its pointwise stabiliser in $G$ is trivial. In this paper we introduce and study an associated graph $\\Sigma(G)$, which we call the Saxl graph of $G$. The vertices of $\\Sigma(G)$ are the points of $\\Omega$, and two vertices are adjacent if they form a base for $G$. This graph encodes some interesting properties of the permutation group. We investigate the connectivity of $\\Sigma(G)$ for a finite transitive group $G$, as well as its diameter, Hamiltonicity, clique and independence numbers, and we present several open problems. For instance, we conjecture that if $G$ is a primitive group with a base of size $2$, then the diameter of $\\Sigma(G)$ is at most $2$. Using a probabilistic approach, we establish the conjecture for some families of almost simple groups. For example, the conjecture holds when $G=S_n$ or $A_n$ (with $n>12$) and the point stabiliser of $G$ is a primitive subgroup. In contrast, we can construct imprimitive groups whose Saxl graph is disconnected with arbitrarily many connected components, or connected with arbitrarily large diameter.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-12-11T09:28:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "permutation group",
      "saxl graph",
      "point stabiliser",
      "conjecture holds",
      "simple groups"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}