Neighbour-transitive codes in Johnson graphs

The Johnson graph (J(v,k)) has, as vertices, the (k) -subsets of a (v) -set (mathcal {V}) and as edges the pairs of (k) -subsets with intersection of size (k-1) . We introduce the notion of a neighbour-transitive code in (J(v,k)) . This is a proper vertex subset (Gamma ) such that the subgroup (G) of graph automorphisms leaving (Gamma ) invariant is transitive on both the set (Gamma ) of ‘codewords’ and also the set of ‘neighbours’ of (Gamma ) , which are the non-codewords joined by an edge to some codeword. We classify all examples where the group (G) is a subgroup of the symmetric group (mathrm{Sym},(mathcal {V})) and is intransitive or imprimitive on the underlying (v) -set (mathcal {V}) . In the remaining case where (Gle mathrm{Sym},(mathcal {V})) and (G) is primitive on (mathcal {V}) , we prove that, provided distinct codewords are at distance at least (3) , then (G) is (2) -transitive on (mathcal {V}) . We examine many of the infinite families of finite (2) -transitive permutation groups and construct surprisingly rich families of examples of neighbour-transitive codes. A major unresolved case remains.