Geodesic
Colorings of the Space $\mathbb R^n$ with Several Forbidden Distances
Matematičeskie zametki, Tome 81 (2007) no. 5, pp. 733-743.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is concerned with the classical problem concerning the chromatic number of a metric space, i.e., the minimal number of colors required to color all points in the space so that the distance (the value of the metric) between points of the same color does not belong to a given set of positive real numbers (the set of forbidden distances). New bounds for the chromatic number are obtained for the case in which the space is $\mathbb R^n$ with a metric generated by some norm (in particular, $l_p$) and the set of forbidden distances either is finite or forms a lacunary sequence.
Keywords: chromatic number, measurable chromatic number, coloring with forbidden distances, lacunary sequence, independence member of a graph, polyhedron
Mots-clés : Diophantine approximation. 
@article{MZM_2007_81_5_a10,
     author = {N. G. Moshchevitin and A. M. Raigorodskii},
     title = {Colorings of the {Space} $\mathbb R^n$ with {Several} {Forbidden} {Distances}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {733--743},
     publisher = {mathdoc},
     volume = {81},
     number = {5},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2007_81_5_a10/}
}
TY  - JOUR
AU  - N. G. Moshchevitin
AU  - A. M. Raigorodskii
TI  - Colorings of the Space $\mathbb R^n$ with Several Forbidden Distances
JO  - Matematičeskie zametki
PY  - 2007
SP  - 733
EP  - 743
VL  - 81
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2007_81_5_a10/
LA  - ru
ID  - MZM_2007_81_5_a10
ER  - 
%0 Journal Article
%A N. G. Moshchevitin
%A A. M. Raigorodskii
%T Colorings of the Space $\mathbb R^n$ with Several Forbidden Distances
%J Matematičeskie zametki
%D 2007
%P 733-743
%V 81
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2007_81_5_a10/
%G ru
%F MZM_2007_81_5_a10
N. G. Moshchevitin; A. M. Raigorodskii. Colorings of the Space $\mathbb R^n$ with Several Forbidden Distances. Matematičeskie zametki, Tome 81 (2007) no. 5, pp. 733-743. http://geodesic.mathdoc.fr/item/MZM_2007_81_5_a10/

[1] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., 11, Springer, Berlin, 2002, 649–666 | MR | Zbl

[2] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | MR | Zbl

[3] J. Pach, P. K. Agarwal, Combinatorial Geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley Sons, New York, 1995 | MR | Zbl

[4] V. Klee, S. Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, The Dolciani Mathematical Expositions, 11, Math. Assoc. America, Washington, DC, 1991 | MR | Zbl

[5] A. Soifer, “Chromatic number of the plane: a historical essay”, Geombinatorics, 1:3 (1991), 13–15 | MR | Zbl

[6] A. Soifer, Mathematical Coloring Book, Center for Excellence in Mathematical Education, Colorado Springs, CO, 1997

[7] A. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosveschenie, Tretya seriya, 8, Izd-vo MTsNMO, M., 2004, 185–221

[8] I. Z. Ruzsa, Zs. Tuza, M. Voigt, “Distance graphs with finite chromatic number”, J. Combin. Theory Ser. B, 85:1 (2002), 181–187 | DOI | MR | Zbl

[9] Y. Katznelson, “Chromatic numbers of Cayley graphs on $\mathbb{Z}$ and recurrence”, Combinatorica, 21:2 (2001), 211–219 | DOI | MR | Zbl

[10] R. K. Akhunzhanov, N. G. Moschevitin, “O khromaticheskom chisle distantsionnogo grafa, svyazannogo s lakunarnoi posledovatelnostyu”, Dokl. RAN, 397:3 (2004), 295–296 | MR

[11] H. Fürstenberg, Y. Katznelson, B. Weiss, “Ergodic theory and configurations in sets of positive density”, Mathematics of Ramsey Theory, Algorithms Combin., 5, Springer, Berlin, 1990, 184–198 | MR | Zbl

[12] J. Bourgain, “A Szemeredi type theorem for sets of positive density in $\mathbb R^k$”, Israel J. Math., 54:3 (1986), 307–316 | DOI | MR | Zbl

[13] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s metrikoi $l_q$”, UMN, 59:5 (2004), 161–162 | MR | Zbl

[14] J.-H. Kang, Z. Füredi, “Distance graphs on $\mathbb{Z}^n$ with $l_1$-norm”, Theoret. Comput. Sci., 319:1–3 (2004), 357–366 | MR | Zbl

[15] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | MR | Zbl

[16] A. M. Raigorodskii, “Problema Erdësha–Khadvigera i khromaticheskie chisla konechnykh geometricheskikh grafov”, Matem. sb., 196:1 (2005), 123–156 | MR | Zbl

[17] Y. G. Chen, T. W. Cusick, “The view-obstruction problem for $n$-dimensional cubes”, J. Number Theory, 74:1 (1999), 126–133 | DOI | MR | Zbl

[18] B. de Mathan, “Numbers contravening a condition in density modulo $1$”, Acta Math. Hungar., 36:3–4 (1980), 237–241 | DOI | MR | Zbl

[19] A. D. Pollington, “On the density of sequence $\{n_k\theta\}$”, Illinois J. Math., 23:4 (1979), 511–515 | MR | Zbl

[20] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, UMN, 55:2 (2000), 147–148 | MR | Zbl