M.Sc Student | Merksamer Yael |
---|---|

Subject | Two Dimensional Cluster Error-Correcting Codes |

Department | Department of Computer Science |

Supervisor | Professor Tuvi Etzion |

We consider various coloring problems of the points of .

It is known that at least colors ( colors) are required to color the points of , such that the -distance between any two points, colored with the same color, is at least (at least ). In this work we characterize all the colorings which attain these bounds.

We consider the problem of coloring the points of , such for any two points colored with the same color, whose -distance is smaller than , the -distance between them is at least . We give lower bounds on the number of colors required and show colorings which attain these bounds.

For , the *tristance* is a generalization of the -distance on to a quality that reflects the
relative dispersion of three points rather than two. In this work we prove that
at least colors are required to color the
points of , such that the tristance between
any three distinct points, colored with the same color, is at least . We prove that colors are required if the
tristance is at least . For the first case we
show an infinite family of colorings with colors
and conjecture that these are the only colorings with colors.

These problems have applications in two-dimensional cluster error-correcting codes. They also have combinatorial interest, as the coloring structures obtained are generalizations of perfect codes of in the -metric and tiling of with Lee spheres.