On metric properties of maps between Hamming spaces and related graph homomorphisms

摘要

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 fin apart in Hamming distance. This is a relaxation of the classical problem of constructing error-correcting codes, which corresponds to alpha = 0. Existence of an (alpha,beta)-map is equivalent to existence of a graph homomorphism H(k, alpha k) -> (H) over bar (n, beta n), where H(n, d) is a Hamming graph with vertex set {0,1}(n) and edges connecting vertices differing in d or fewer entries. This paper proves impossibility results on achievable parameters (alpha,beta) in the regime of n, k -> infinity with a fixed ratio n/k = p. This is done by developing a general criterion for existence of graph-homomorphism based on the semi-definite relaxation of the independence number of a graph (known as the Schrijver's 0-function). The criterion is then evaluated using some known and some new results from coding theory concerning the theta-function of Hamming graphs. As an example, it is shown that if beta > 1/2 and n/k - integer, the n/k-fold repetition map achieving alpha = beta is asymptotically optimal. Finally, constraints on configurations of points and hyper planes in projective spaces over F-2 are derived. (C) 2016 Elsevier Inc. All rights reserved.