DIMACS TR: 98-01

Closed Sets and Generators in Ternary Hamming Spaces

Authors: Endre Boros, Peter L. Hammer, Frederica Ricca and Bruno Simeone


The $n$-dimensional ternary Hamming space is $\TT^n$, where $\TT=\{ 0, 1,2\}$. Three points in $\TT^n$ form a line if they have in common exactly $n-1$ compone nts. A subset of $\TT^n$ is closed if, whenever it contains two points of a line, it contains also the third one. A generator is a set, whose closure is $\TT^n$. In this paper, we investigate se veral properties of closed sets and generators. Two alternative proofs of our main result, stating that the minimum cardinality of a generator is $2^n$, are provided.

The present study was motivated by some combinatorial questions concerning origin-destination matrices in transportation systems.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-01.ps.gz

DIMACS Home Page