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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Up ↑

%d bloggers like this: