2023/07/19 by Dean Crnković, Daniel R. Hawtin, Crnković, Dean +5
Computer Science · Mathematics · #05E18 #20B25 #Coding theory and cryptography #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Finite Group Theory Research
paper · pdf · doi:10.48550/arxiv.2307.09752
openalex publication_date 2023/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 C0,C1,…,Cs of the distance partition \C=C0,C1,…,Cρ\, where ρ 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 Ω 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 Ω we characterise C in terms of certain parameters. We then assume that \rm Aut(C) acts transitively on Ω, 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 Ω. We then assume that C is a code in an odd graph and \rm Aut(C) acts imprimitively on Ω and characterise C in terms of certain parameters. We give examples in each of these cases and pose several open problems.