Хроматические числа пространств. Рубрика в журнале - Труды Московского физико-технического института
О дистанционных графах с большим хроматическим и малым кликовым числами
Статья научная
Работа связана с изучением хроматического числа χ (Rn) евклидова пространства, которое определяется как минимальное количество цветов, необходимых для такой покраски точек Rn, что любые две точки, отстоящие друг от друга на расстояние 1, покрашены в разные цвета. Известно, чтоχ (Rn) ≥ (ζ+o(1))n, где ζ = 1.239... Это равносильно существованию n-мерного дистанционного графа (вершины - точки, ребра - отрезки длины 1) с хроматическим числом (ζ +o(1))n. Мы доказываем гораздо большее: существуют дистанционные графы с хроматическим числом (ζ +o(1))n и без клик растущего размера.
Бесплатно
О плотнейших множествах без расстояния единица в пространствах малых размерностей
Статья научная
В данной работе мы исследуем значение максимальной верхней плотности под- множества Rd, свободного от расстояния 1, при d ≤ 8. Мы получаем новые нижние оценки указанной величины и применяем полученные результаты к решению одной задачи геометрической теории Рамсея.
Бесплатно
О хроматическом числе пространства Qn
Статья научная
Работа посвящена классической проблеме Нелсона-Хадвигера о хроматическом числе пространства. Мы рассматриваем обобщение проблемы на случай пространства Qn. Мы вводим новую величину χ aff(Qn), равную максимальному значению хроматического числа дистанционного графа, вершины которого расположены в некотором аффинном подпространстве размерности n некоторого пространства Qm, а ребра порождены рациональным расстоянием. Доказаны новые оценки для этой величины.
Бесплатно
