О числе рёбер в индуцированных подграфах специальных дистанционных графов
24 августа 2020 года
21:11
О числе рёбер в индуцированных подграфах специальных дистанционных графов
Текст новости:
и степень её разрабо­ танности Рассмотрение дистанционных графов глубоко мотивировано некоторы­ ми знаменитыми задачами комбинаторной геометрии, в частности — задачей Нельсона-Эрдеша-Хадвигера, проблемой Борсука, задачей о кодах с запре­ щенным расстоянием и другими. В задаче Нельсона-Эрдеша-Хадвигера ста­ вится вопрос о хроматическом числе пространства R𝑛 : минимальном числе цветов, в которые можно раскрасить 𝑛-мерное евклидово пространство так, чтобы никакие две точки, отстоящие друг от друга на расстояние 1, не бы­ ли окрашены в один и тот же цвет (см. [1] – [2]). С точки зрения теории графов, рассматривается задача о хроматическом числе бесконечного графа, вершинами которого являются все точки пространства R𝑛 , а ребро проводит­ ся между точками на расстоянии 1. Теорема Эрдеша–де Брейна утверждает, что бесконечный граф можно раскрасить в 𝑘 цветов тогда и только тогда, когда в 𝑘 цветов можно раскрасить каждый его конечный подграф (см. [3]). Тем самым, достаточно изучать хроматические числа конечных дистанцион­ ных графов — вершины дистанционного графа представляют собой конеч­ ное множество точек пространства R𝑛 , а ребро проводится в том и только том случае, если точки находятся на некотором фиксированном расстоянии друг от друга. Вообще, подобные графы обычно называют полными дистан­ ционными графами. Смысл слова «дистанционный» понятен: ребра графа задаются парами точек, отстоящих друг от друга на некоторое расстояние –– «дистанцию». А полнота понимается в том смысле, что мы провели в графе все возможные ребра. В данной работе мы сконцентрируемся на рассмотрении специально­ го дистанционного графа 𝐺 (𝑛,3,1), вершинами которого являются точки в 𝑛-мерном булевом кубе, у которых ровно 3 единицы, а ребро между таки­ ми вершинами проводится тогда и только тогда, когда евклидово расстояние между соответствующими точками равно 2, или, что то же самое, когда ска­ лярное произведение соответствующих векторов равно 1. Можно сформули­ ровать данное определение в комбинаторных терминах, а именно, вершинами данного графа являются все возможные трехэлементные подмножества мно­ жества ℛ𝑛 = {1, 2, . . . , 𝑛}, а ребро проводится между подмножествами, имею­ щими ровно один общий элемент. Видимо, впервые подобные дистанционные 3

Текст со страницы (автоматическое получение):
Автоматическая система мониторинга и отбора информации
Источник