PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 25-31
DOI: https://doi.org/10.7151/dmgt.1641

Coloring Some Finite Sets in ℝⁿ

József Balogh Department of Mathematics, University of Illinois, Urbana, IL 61801, USA

Alexandr Kostochka Department of Mathematics, University of Illinois, Urbana, IL, 61801, USA Sobolev Institute of Mathematics, Novosibirsk, Russia

Andrei Raigorodskii Department of Mechanics and Mathematics, Moscow State University, Leninskie gory, Moscow, 119991, Russia Department of Discrete Mathematics, Moscow Institute of Physics and Technology, Dolgoprudny, Russia

Abstract

This note relates to bounds on the chromatic number χ(ℝⁿ) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝⁿ so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs G_n in ℝⁿ was introduced showing that χ(ℝⁿ) ≥ χ(G_n) ≥ (1+o(1)) n²/6 . For many years, this bound has been remaining the best known bound for the chromatic numbers of some low-dimensional spaces. Here we prove that χ(G_n) ~ n²/6 and find an exact formula for the chromatic number in the case of n = 2^k and n = 2^k − 1 .

Keywords: chromatic number, independence number, distance graph

2010 Mathematics Subject Classification: 52C10, Secondary: 05C15.

References

[1]	N.G. de Bruijn and P. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet. (A) 54 (1951) 371--373.
[2]	P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981) 357--368, doi: 10.1007/BF02579457.
[3]	A.B. Kupavskiy, On coloring spheres embedded into ℝn , Sb. Math. 202(6) (2011) 83--110.
[4]	A.B. Kupavskiy and A.M. Raigorodskii, On the chromatic number of ℝ9, J. Math. Sci. 163(6) (2009) 720--731, doi: 10.1007/s10958-009-9708-4.
[5]	D.G. Larman, A note on the realization of distances within sets in Euclidean space, Comment. Math. Helv. 53 (1978) 529--535, doi: 10.1007/BF02566096.
[6]	D.G. Larman and C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972) 1--24, doi: 10.1112/S0025579300004903 .
[7]	N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory (A) 51 (1989) 24--42, doi: 10.1016/0097-3165(89)90074-5.
[8]	A.M. Raigorodskii, On the chromatic number of a space, Russian Math. Surveys 55 (2000) N2, 351--352, doi: 10.1070/RM2000v055n02ABEH000281.
[9]	A.M. Raigorodskii, The problems of Borsuk and Grünbaum on lattice polytopes, Izv. Math. 69(3) (2005) 81--108. English transl. Izv. Math. 69(3) (2005) 513--537, doi: 10.1070/IM2005v069n03ABEH000537.

Received 15 December 2011
Revised 10 May 2012
Accepted 10 May 2012