Математические заметки Том 101 выпуск 3 март 2017 УДК 519.1 О нижних оценках хроматических чисел дистанционных графов с большим обхватом А.А. Сагдеев Получены некоторые конкретные нижние экспоненциальные оценки хроматических чисел дистанционных графов с большим обхватом. <...> В данной статье мы получим некоторые конкретные нижние экспоненциальные оценки хроматических чисел дистанционных графов с большим обхватом. <...> Но прежде, чем формулировать результаты, напомним определения основных объектов, с которыми мы будем работать, а также дадим небольшую историческую справку о возникновении данной задачи и родственных ей проблем. <...> Хроматическим числом χ(Rn) пространства Rn называется минимальное число цветов, которые требуются для такой раскраски точек пространства, чтобы не было точек одного цвета на единичном расстоянии (на самом деле, вместо единичного расстояния можно было бы “запретить” любое другое). <...> Задача о нахождении хроматического числа плоскости была поставлена Нельсоном в 1950 г. (см. <...> А.А. Сагдеев, 2017 c 430 О НИЖНИХ ОЦЕНКАХ ХРОМАТИЧЕСКИХ ЧИСЕЛ Граф G = (V,E) называется дистанционным, если V – подмножество в Rn, а E ⊆ {x, y} | x, y ∈ V, |x−y| = a для некоторого фиксированного a. <...> Такие графы естественно возникают при рассмотрении задачи о хроматическом числе χ(Rn), так как в соответствии с теоремой Эрдёша–де Брейна (см. <...> ) хроматическое число пространства равно хроматическому числу некоторого конечного дистанционного графа в этом пространстве. <...> Определим дистанционный граф G(n,m, l) следующим образом: его вершинами являются все точки в Rn, у которых ровно m координат равны единице, а оставшиеся n−m координат равны нулю. <...> ) доказал теорему о том, что для любых k и l можно построить граф, хроматическое число которого больше k, при этом он не содержит циклов длины, меньшей либо равной l (т.е. его обхват больше l). <...> Нам интересно, как могут вести себя хроматические числа дистанционных графов (в частности, графов G(n <...>