11–12 МАТЕМАТИКА УДК 519 О ХРОМАТИЧЕСКИХ ЧИСЛАХ ПРОСТРАНСТВ МАЛОЙ РАЗМЕРНОСТИ © 2017 г. Д. <...> Козловым 09.08.2016 г. Поступило 20.09.2016 г. Найдены новые нижние оценки минимального числа цветов, в которые можно так покрасить все точки евклидова пространства, чтобы между точками одного цвета не было расстояния 1. <...> DOI: 10.7868/S0869565217010030 Одной из самых известных задач комбинаторной геометрии является проблема Нелсона– Хадвигера, сформулированная в середине ХХ века (см. <...> ). Она состоит в отыскании хроматического числа χ R () n евклидова пространства, равного наименьшему количеству цветов, в которые Rn можно так покрасить все точки , чтобы между точками одного цвета не было расстояния 1. <...> Во всех () 2 R1 остальных размерностях есть лишь верхние и нижние оценки. <...> По большей части эти улучшения получены с помощью компьютерного счета, что несколько обесценивает их. <...> Нам удалось добиться дальнейших продвижений в задаче и показать, что 1 Санкт-Петербургский государственный университет 2 Московский физико-технический институт (государственный университет), Долгопрудный Московской обл. <...> 3 Universitй de Genиve, Switzerland 4 Московский государственный университет им. <...> 30, 12 RR RR 910 11 Более того, эти оценки суть частные случаи одного весьма общего результата, о котором мы поговорим в следующем разделе. <...> ИДЕЯ ДОКАЗАТЕЛЬСТВА И ФОРМУЛИРОВКА ОБЩЕЙ ТЕОРЕМЫ Напомним, что граф V ⊂ Rn =− = {{ , } :xy x y χ() G станционным графом в пространстве , если , а GV E является диRn =, () значено евклидово расстояние и – положительное вещественное число. <...> Напомним также, что хроматическое число графа – это минимальное количество цветов, в которые можно так покрасить все вершины графа, чтобы любые две вершины, соединенные ребром, имели разные цвета. <...> Понятно, что если – дистанционный Ea} , где модулем обоa G G граф в , тоRn χ≥χR n () (G) . называется максимальное число , при котором существует независимое множество вершин графа мощности , т.е. такое множество вершин, что никакие две из них не соединены ребром <...>