Premium
Configurations Maximizing the Number of Pairs of Hamming‐Adjacent Lattice Points
Author(s) -
Kleitman D. J.,
Krieger M. M.,
Rothschild B. L.
Publication year - 1971
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm1971502115
Subject(s) - mathematics , combinatorics , lexicographical order , lattice (music) , cube (algebra) , hamming distance , hypercube , hamming code , algorithm , physics , decoding methods , acoustics , block code
The following question is considered: Which sets of k lattice points among the n d points in a d ‐dimensional cube of length n maximize the number of pairs of points differing in only one coordinate? It is shown that maximal configurations for any ( d, n, k ) are obtained by choosing the first k points in a lexicographic ordering of the points by coordinates. Some possible generalizations of the problem are discussed.