Optimal Tristance Anticodes in Certain Graphs
| dc.creator | Etzion, Tuvi | |
| dc.creator | Schwartz, Moshe | |
| dc.creator | Vardy, Alexander | |
| dc.date | 2004-06-12 | |
| dc.date.accessioned | 2026-07-07T05:09:11Z | |
| dc.date.available | 2026-07-07T05:09:11Z | |
| dc.description | For $z_1,z_2,z_3 \in \Z^n$, the \emph{tristance} $d_3(z_1,z_2,z_3)$ is a generalization of the $L_1$-distance on $\Z^n$ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticode $\cA_d$ of diameter $d$ is a subset of $\Z^n$ with the property that $d_3(z_1,z_2,z_3) \leq d$ for all $z_1,z_2,z_3 \in \cA_d$. An anticode is optimal if it has the largest possible cardinality for its diameter $d$. We determine the cardinality and completely classify the optimal tristance anticodes in $\Z^2$ for all diameters $d \ge 1$. We then generalize this result to two related distance models: a different distance structure on $\Z^2$ where $d(z_1,z_2) = 1$ if $z_1,z_2$ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when $\Z^2$ is replaced by the hexagonal lattice $A_2$. We also investigate optimal tristance anticodes in $\Z^3$ and optimal quadristance anticodes in $\Z^2$, and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go. | |
| dc.description | 33 pages, 12 figures | |
| dc.identifier | https://arxiv.org/abs/math/0406246 | |
| dc.identifier | http://arxiv.org/abs/math/0406246 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71538 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C12, 05B40; 94B25 | |
| dc.title | Optimal Tristance Anticodes in Certain Graphs | |
| dc.type | text |