On Golomb-Welch conjecture

Peter Horak, University of Washington at Tacoma

Golomb and Welch have conjectured that a perfect e-error correcting Lee code of length n, n > 2, over a large alphabet exists only for e = 1. A stronger (geometric) version of the conjecture says that there is no tiling of En, the n-dimensional Euclidean space, by "cubistic cross polytopes" of radius > 1.

Despite a lot of effort by researchers both in graph theory and in coding theory the conjecture is still open although there are plenty of partial results supporting the conjecture.

In this talk we will discuss most recent results and several variations of the conjecture; some of them motivated by an application in computer science.

back to EIDMA Seminar Combinatorial Theory announcements