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 , which has as vertices the -subsets of and two vertices are adjacent if they intersect in all but one element. A code of is a set of vertices, and it is -perfect if the spheres of radius with centers at the elements of form a partition of the entire set of vertices of . For example, we could take to be all the vertices to obtain a 0-perfect code of . Alternatively, if is a -subset, then is a -perfect code of . Both of these examples are considered trivial examples. There is a third type of trivial example where and is odd. We take two disjoint -subsets and , and we see that forms a -perfect code.
These examples are they only perfect codes known of !
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 . Let be a prime. Then Tuvi Etzion (1996) proved that there are no -perfect codes in , none in for , and none in for .