Back to Search
Start Over
On metric properties of maps between Hamming spaces and related graph homomorphisms.
- Source :
-
Journal of Combinatorial Theory - Series A . Jan2017, Vol. 145, p227-251. 25p. - Publication Year :
- 2017
-
Abstract
- A mapping of k -bit strings into n -bit strings is called an ( α , β ) -map if k -bit strings which are more than αk apart are mapped to n -bit strings that are more than βn apart in Hamming distance. This is a relaxation of the classical problem of constructing error-correcting codes, which corresponds to α = 0 . Existence of an ( α , β ) -map is equivalent to existence of a graph homomorphism H ¯ ( k , α k ) → H ¯ ( n , β n ) , where H ( n , d ) is a Hamming graph with vertex set { 0 , 1 } n and edges connecting vertices differing in d or fewer entries. This paper proves impossibility results on achievable parameters ( α , β ) in the regime of n , k → ∞ with a fixed ratio n k = ρ . This is done by developing a general criterion for existence of graph-homomorphism based on the semi-definite relaxation of the independence number of a graph (known as the Schrijver's θ -function). The criterion is then evaluated using some known and some new results from coding theory concerning the θ -function of Hamming graphs. As an example, it is shown that if β > 1 / 2 and n k – integer, the n k -fold repetition map achieving α = β is asymptotically optimal. Finally, constraints on configurations of points and hyperplanes in projective spaces over F 2 are derived. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH theory
*HAMMING distance
*METRIC spaces
*MATHEMATICAL mappings
*HOMOMORPHISMS
Subjects
Details
- Language :
- English
- ISSN :
- 00973165
- Volume :
- 145
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series A
- Publication Type :
- Academic Journal
- Accession number :
- 118422512
- Full Text :
- https://doi.org/10.1016/j.jcta.2016.08.005