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

详细信息    查看全文

• 作者：Yury Polyanskiy ^{yp@mit.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Error-correcting codes ; Graph homomorphism ; Schrijver's θ-function ; Projective geometry over F2F2
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：145
• 期：Complete
• 页码：227-251
• 全文大小：532 K

文摘

A mapping of k-bit strings into n  -bit strings is called an (α,β)$(\alpha ,\beta )$-map if k-bit strings which are more than αk apart are mapped to n-bit strings that are more than βn   apart in Hamming distance. This is a relaxation of the classical problem of constructing error-correcting codes, which corresponds to 0579c8548e73fdd0b138e22" title="Click to view the MathML source">α=0$\alpha =0$. Existence of an (α,β)$(\alpha ,\beta )$-map is equivalent to existence of a graph homomorphism $\overline{H}(k,\alpha k)\to \overline{H}(n,\beta n)$, where H(n,d)$H(n,d)$ is a Hamming graph with vertex set 5e23bfcbbbbe454d496e3001" title="Click to view the MathML source">{0,1}ⁿ${\{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→∞$n,k\to \infty$ with a fixed ratio 050">$\frac{n}{k}=\rho$. 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 θ-function). The criterion is then evaluated using some known and some new results from coding theory concerning the θ  -function of Hamming graphs. As an example, it is shown that if 05" title="Click to view the MathML source">β>1/2$\beta >1/2$ and $\frac{n}{k}$ – integer, the $\frac{n}{k}$-fold repetition map achieving 5e784d65b46d6ad4df2ffb" title="Click to view the MathML source">α=β$\alpha =\beta$ is asymptotically optimal.

050">Finally, constraints on configurations of points and hyperplanes in projective spaces over 0557" title="Click to view the MathML source">F₂${\mathbb{F}}_2$ are derived.