DocumentCode :
2050549
Title :
On the optimality of coloring with a lattice
Author :
Merksamer, Yael ; Etzion, Tuvi
Author_Institution :
Dept. of Electr. Eng. Syst., Tel Aviv Univ., Israel
fYear :
2004
fDate :
27 June-2 July 2004
Firstpage :
21
Abstract :
For z1, z2, z3 ∈ Z2, the tristance d3(z1, z2, z3) is a generalization of the L1-distance on Z2 to a quality that reflects the relative dispersion of three points rather than two. We prove that at least 3k2 colors are required to color the points of Z2, such that the tristance between any three distinct points, colored with the same color, is at least 4k. We also prove that 3k2+3k+1 colors are required if the tristance is at least 4k+2. For the first case we show an infinite family of colorings with 3k2 colors and conjecture that these are the only colorings with 3k2 colors.
Keywords :
error correction codes; interleaved codes; optimisation; interleaving scheme; optimal coloring; two-dimensional cluster error-correcting code; Computer science; Error correction; Error correction codes; Lattices; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on
Print_ISBN :
0-7803-8280-3
Type :
conf
DOI :
10.1109/ISIT.2004.1365058
Filename :
1365058
Link To Document :
بازگشت