{
  "id": "2307.09752",
  "version": "v1",
  "published": "2023-07-19T05:24:59.000Z",
  "updated": "2023-07-19T05:24:59.000Z",
  "title": "Neighbour-transitive codes in Kneser graphs",
  "authors": [
    "Dean Crnković",
    "Daniel R. Hawtin",
    "Nina Mostarac",
    "Andrea Švob"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A code $C$ is a subset of the vertex set of a graph and $C$ is $s$-neighbour-transitive if its automorphism group ${\\rm Aut}(C)$ acts transitively on each of the first $s+1$ parts $C_0,C_1,\\ldots,C_s$ of the distance partition $\\{C=C_0,C_1,\\ldots,C_\\rho\\}$, where $\\rho$ is the covering radius of $C$. While codes have traditionally been studied in the Hamming and Johnson graphs, we consider here codes in the Kneser graphs. Let $\\Omega$ be the underlying set on which the Kneser graph $K(n,k)$ is defined. Our first main result says that if $C$ is a $2$-neighbour-transitive code in $K(n,k)$ such that $C$ has minimum distance at least $5$, then $n=2k+1$ (i.e., $C$ is a code in an odd graph) and $C$ lies in a particular infinite family or is one particular sporadic example. We then prove several results when $C$ is a neighbour-transitive code in the Kneser graph $K(n,k)$. First, if ${\\rm Aut}(C)$ acts intransitively on $\\Omega$ we characterise $C$ in terms of certain parameters. We then assume that ${\\rm Aut}(C)$ acts transitively on $\\Omega$, first proving that if $C$ has minimum distance at least $3$ then either $K(n,k)$ is an odd graph or ${\\rm Aut}(C)$ has a $2$-homogeneous (and hence primitive) action on $\\Omega$. We then assume that $C$ is a code in an odd graph and ${\\rm Aut}(C)$ acts imprimitively on $\\Omega$ and characterise $C$ in terms of certain parameters. We give examples in each of these cases and pose several open problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-19T05:24:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E18",
      "20B25"
    ],
    "keywords": [
      "kneser graph",
      "neighbour-transitive code",
      "odd graph",
      "minimum distance",
      "first main result says"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}