Perfect codes of the Johnson scheme

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.

Advertisements

Up ↑