Neighbour-transitive codes in Kneser graphs

Dean Crnković, Daniel R. Hawtin, Nina Mostarac, Andrea Švob

Published 2023-07-19Version 1

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.