Graph homomorphisms, Schrijver's theta-function and maps between Hamming spaces.

The classical question in coding theory is to find the maximal number of points in the Hamming space with a given lower bound on pairwise distance. The best known upper bound on this number is obtained via Delsarte's linear programming, which in fact is equivalent to Schrijver-Lovasz SDP relaxation of the maximal independent set problem.

In this talk I will first give a brief account of how the best asymptotic bounds on codes were derived (the McEliece-Rodemich-Rumsey-Welch or the JPL-bound).

Then I will introduce a new problem that I currently study. Concretely, a mapping of k-bit strings into n-bit strings is called an $(\alpha,\beta)$-map if $k$-bit strings which are more than $\alpha k$ apart are mapped to $n$-bit strings that are more than $\beta n$ apart. This is clearly a relaxation of the classical coding problem ($\alpha=0$).

This question is equivalent to existence of graph homomorphisms between certain graphs on the hypercube. Thus, I will try to explain what graph homomorphisms are, and what are the known and new tools to prove non-existence of them. Finally, I will show how to use linear programming methods to produce upper bounds on rate in this new problem.

There are a number of interesting connections arising. First the results imply that list-decoders experience a certain phase-transition at radius $1/4$: the lists start to have large (worst-case) diameter. Second, our bound can be seen as improvement of a certain natural bound which replaces Turan's theorem with a beautiful construction of Samorodnitsky.
Third, as a question of embedding of Hamming spaces there are some topological obstructions to such embeddings. In particular, I will mention how Kneser conjecture can be applied here.