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 hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si1.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=192a5ab18adce2b778d6f07807cbf876" title="Click to view the MathML source">(α,β)hContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">hy="false">(α,βhy="false">)h>-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 hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si2.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=671e89c670579c8548e73fdd0b138e22" title="Click to view the MathML source">α=0hContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">α=0h>. Existence of an hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si1.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=192a5ab18adce2b778d6f07807cbf876" title="Click to view the MathML source">(α,β)hContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">hy="false">(α,βhy="false">)h>-map is equivalent to existence of a graph homomorphism hmlsrc">w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si3.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=d046a8890d3e60ac4d9311ff9ce82295">height="19" width="152" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300772-si3.gif">hContainer hidden">hCode">h altimg="si3.gif" overflow="scroll">w>Hw>w>hy="false">¯w>hy="false">(k,αkhy="false">)hy="false">→w>Hw>w>hy="false">¯w>hy="false">(n,βnhy="false">)h>, where hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si4.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=a60d896e277f97b7752b5bef4cc5406e" title="Click to view the MathML source">H(n,d)hContainer hidden">hCode">h altimg="si4.gif" overflow="scroll">Hhy="false">(n,dhy="false">)h> is a Hamming graph with vertex set hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si5.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=6f11b9d65e23bfcbbbbe454d496e3001" title="Click to view the MathML source">{0,1}ⁿhContainer hidden">hCode">h altimg="si5.gif" overflow="scroll">w>hy="false">{0,1hy="false">}w>w>nw>h> and edges connecting vertices differing in d or fewer entries.

This paper proves impossibility results on achievable parameters hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si1.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=192a5ab18adce2b778d6f07807cbf876" title="Click to view the MathML source">(α,β)hContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">hy="false">(α,βhy="false">)h> in the regime of hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si6.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=171462487b5900edf6f3639ca9de83aa" title="Click to view the MathML source">n,k→∞hContainer hidden">hCode">h altimg="si6.gif" overflow="scroll">n,khy="false">→∞h> with a fixed ratio hmlsrc">w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si352.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=b802b2eebcab5acb8d66b8463482d050">height="17" width="43" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300772-si352.gif">hContainer hidden">hCode">h altimg="si352.gif" overflow="scroll">nk=ρh>. 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 hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si112.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=522846aaf5350e1e92ca3f73ff7f3605" title="Click to view the MathML source">β>1/2hContainer hidden">hCode">h altimg="si112.gif" overflow="scroll">β>1hy="false">/2h> and hmlsrc">w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si9.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=11c7f5963e5721e6cb3320db4d3f02af">height="16" width="11" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300772-si9.gif">hContainer hidden">hCode">h altimg="si9.gif" overflow="scroll">nkh> – integer, the hmlsrc">w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si9.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=11c7f5963e5721e6cb3320db4d3f02af">height="16" width="11" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0097316516300772-si9.gif">hContainer hidden">hCode">h altimg="si9.gif" overflow="scroll">nkh>-fold repetition map achieving hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si10.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=009b3b12fb5e784d65b46d6ad4df2ffb" title="Click to view the MathML source">α=βhContainer hidden">hCode">h altimg="si10.gif" overflow="scroll">α=βh> is asymptotically optimal.

Finally, constraints on configurations of points and hyperplanes in projective spaces over hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0097316516300772&_mathId=si11.gif&_user=111111111&_pii=S0097316516300772&_rdoc=1&_issn=00973165&md5=69a1a114ff17eca1376c34506c550557" title="Click to view the MathML source">F₂hContainer hidden">hCode">h altimg="si11.gif" overflow="scroll">w>hvariant="double-struck">Fw>w>2w>h> are derived.