Johnson scheme – SymOmega

One of the most intriguing conjectures in the theory of association schemes was posed by Delsarte in his 1973 doctoral thesis: does there exist a nontrivial perfect code of the Johnson scheme?

The Johnson scheme is just the set of distance relations on the Johnson graph $J(n, k)$ , which has as vertices the $k$ -subsets of $\{1,2,\ldots,n\}$ and two vertices are adjacent if they intersect in all but one element. A code of $J(n, k)$ is a set $C$ of vertices, and it is $e$ -perfect if the spheres of radius $e$ with centers at the elements of $C$ form a partition of the entire set of vertices of $J(n, k)$ . For example, we could take $C$ to be all the vertices to obtain a 0-perfect code of $J(n, k)$ . Alternatively, if $v$ is a $k$ -subset, then $C:=\{v\}$ is a $k$ -perfect code of $J(n,k)$ . Both of these examples are considered trivial examples. There is a third type of trivial example where $n = 2k$ and $k$ is odd. We take two disjoint $k$ -subsets $v_1$ and $v_2$ , and we see that $C:=\{v_1,v_2\}$ forms a $\tfrac{1}{2}(k-1)$ -perfect code.

These examples are they only perfect codes known of $J(n,k)$ !

An excellent survey of this problem can be found in the Master’s thesis of Natalia Silberstein, but we will state just a few of the results which have established large steps towards proving Delsarte’s Conjecture. Cornelis Roos (1983) proved that if an e-perfect code of J(n, k) exists, then $n\le (k-1)\frac{2e+1}{e}$ . Let $p$ be a prime. Then Tuvi Etzion (1996) proved that there are no $e$ -perfect codes in $(2k+p,k)$ , none in $J(2k+2p,k)$ for $p >3$ , and none in $J(2k+3p,k)$ for $p>5$ .

Tag: Johnson scheme

Perfect codes of the Johnson scheme