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
.