1. Distance graph on <f>Zn</f> with <f>ℓ1</f> norm
- Author
-
Füredi, Zoltán and Kang, Jeong-Hyun
- Subjects
- *
COMBINATORIAL geometry , *COMBINATORICS , *DISCRETE geometry , *ARITHMETICAL algebraic geometry - Abstract
A long-standing open problem in combinatorial geometry is the chromatic number of the unit-distance graph in
Rn ; here points are adjacent if their distance in theℓ2 norm is 1. Forn=2 , we know the answer is between 4 and 7. Little is known about other dimensions. The subgraphs induced by the rational points have been studied with limited success in small dimensions.We consider the analogous problem on then -dimensional integer grid with fixed distance in theℓ1 norm. That is, we make two integer grid points adjacent if the sum of the absolute differences in their coordinate values isr . Let the chromatic number of this graph beχ(Z,r) .The main results of this paper are (i)χ(Zn,2)=2n for alln , and (ii)(1.139)n⩽χ(Zn,r)⩽(1/√ of 2πn)(5e)n for alln and evenr . We also give bounds useful for small values ofn andr . We also consider the lower and upper bounds on then -dimensional real space with unit distance underℓp norm for1⩽p⩽∞ . [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF