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$.