Optimal tristance anticodes in certain graphs

For z1,z2,z3∈Zn, the tristance d3(z1,z2,z3) is a generalization of the L1-distance on Zn to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticode Ad of diameter d is a subset of Zn with the property that d3(z1,z2,z3)⩽d for all z1,z2,z3∈Ad. 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 Z2 for all diameters d⩾1. We then generalize this result to two related distance models: a different distance structure on Z2 where d(z1,z2)=1 if z1,z2 are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z2 is replaced by the hexagonal lattice A2. We also investigate optimal tristance anticodes in Z3 and optimal quadristance anticodes in Z2, 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.