Noga Alon, Princeton University and Tel Aviv University

Abstract

What is the maximum possible number of words in a binary code of length n so that there is no Hamming ball of radius (1/4+epsilon)n containing more than two words ? I will show that the answer is Theta(1/epsilon^{3/2}). A crucial ingredient in the proof is a construction of a family of Cayley graphs which is useful in tackling several additional extremal problems in Graph Theory and Geometry. Joint work with Bukh and Polyanskiy.