Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 5, 2006 | public
Journal Article Open

Optimal Interleaving on Tori


This paper studies $t$-interleaving on two-dimensional tori. Interleaving has applications in distributed data storage and burst error correction, and is closely related to Lee metric codes. A $t$-interleaving of a graph is defined as a vertex coloring in which any connected subgraph of $t$ or fewer vertices has a distinct color at every vertex. We say that a torus can be perfectly t-interleaved if its t-interleaving number (the minimum number of colors needed for a t-interleaving) meets the sphere-packing lower bound, $\lceil t^2/2 \rceil$. We show that a torus is perfectly t-interleavable if and only if its dimensions are both multiples of $\frac{t^2+1}{2}$ (if t is odd) or t (if t is even). The next natural question is how much bigger the t-interleaving number is for those tori that are not perfectly t-interleavable, and the most important contribution of this paper is to find an optimal interleaving for all sufficiently large tori, proving that when a torus is large enough in both dimensions, its t-interleaving number is at most just one more than the sphere-packing lower bound. We also obtain bounds on t-interleaving numbers for the cases where one or both dimensions are not large, thus completing a general characterization of t-interleaving numbers for two-dimensional tori. Each of our upper bounds is accompanied by an efficient t-interleaving scheme that constructively achieves the bound.

Additional Information

©2006 Society for Industrial and Applied Mathematics. Received by the editors November 10, 2004; accepted for publication (in revised form) May 15, 2006; published electronically December 5, 2006. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by NSF grant CCR-TC-0208975. A one-page abstract presenting part of the results in this paper appeared in the Proceedings of the IEEE International Symposium on Information Theory, held in Chicago, 2004. The authors thank the anonymous reviewers for their very careful and thoughtful comments.


Files (554.6 kB)
Name Size Download all
554.6 kB Preview Download

Additional details

August 22, 2023
October 16, 2023