Accession Number : AD0704111

Title :   NOTES ON COMBINATORICS: A NEW LOWER BOUND FOR COVERINGS BY ROOK DOMAINS,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Johnson,S. M.

Report Date : MAR 1970

Pagination or Media Count : 32

Abstract : Let (V sub k, sup n) be the set of all n-tuples a sub 1, a sub 2, ..., a sub n where each a sub i ranges over 0, 1, ... k-1. These can be considered as coordinate vectors of points in an n-cube with k points on a side. The Hamming metric d(x,y) is defined to be the number of coordinates in which x and y differ. A Hamming sphere about x of radius r (or a rook domain) is the set of all y in (V sub k, sup n) such that d(x,y) = or < r. In previous papers the author has refined estimates of how many nonintersecting Hamming spheres can be packed into the space. This gave greatly improved upper bounds on the size of error-correcting coes, a subject of growing importance in the problem of error free transmission of information subject to noise. In the present paper somewhat analogous methods are used to the dual problem of improving lower bounds on the number sigma(n,r,k) of rook domains or Hamming spheres which are needed to cover the whole space, where now the spheres may intersect. (Author)

Descriptors :   (*COMBINATORIAL ANALYSIS, THEOREMS), (*CODING, ERRORS), SET THEORY, TOPOLOGY

Subject Categories : Theoretical Mathematics
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE