Экстремальные характеристики обобщённых графов Джонсона, их случайных подграфов и некоторых других дистанционных графов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Синельников-Мурылев Петр Сергеевич

• Синельников-Мурылев Петр Сергеевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Синельников-Мурылев Петр Сергеевич

Введение

Глава 1. Графы Джонсона

1.1 Основной объект

1.2 Кликовые числа, числа независимости и хроматические числа графов Джонсона

1.2.1 Кликовые числа

1.2.2 Числа независимости

1.2.3 Хроматические числа

1.3 Случайные графы и подграфы

1.3.1 Вступление

1.3.2 Биномиальные случайные графы и подграфы

1.3.3 Числа независимости случайных подграфов графов Джонсона

1.3.4 Кликовые числа случайных подграфов графов Джонсона

1.3.5 Хроматические числа случайных подграфов графов Джонсона

1.4 Графы Джонсона, их случайные подграфы и теория Рамсея

Глава 2. О раскрасках сферы с запрещенным интервалом

расстояний

2.1 История задачи

2.2 Постановка задачи

2.3 Определения и начальные утверждения

2.4 Раскраска локальных конфигураций

2.5 Перебор триангуляций с 7-раскрашиваемым квадратом

2.6 Доказательство основного результата

Заключение

Список литературы

Приложение А Текст программы

Приложение Б Конфигурации раскрасок

Приложение В Текст программы

Введение диссертации (часть автореферата) на тему «Экстремальные характеристики обобщённых графов Джонсона, их случайных подграфов и некоторых других дистанционных графов»

Введение

Актуальность. В диссертационной работе изучаются вопросы, связанные с характеристиками так называемых обобщённых графов Джонсона и его случайных подграфов. Основное внимание уделено изучению асимптотики поведения таких характеристик, как число независимости, кликовое число и хроматическое число указанных графов. В работе также рассматриваются вопросы, связанные с тематикой обобщения задачи Хадвигера—Нельсона о хроматическом числе пространства и многообразий в нём. В частности, получены ограничения на радиус сферы, при котором невозможна "правильная" раскраска.

Строгие определения используемых понятий мы дадим в следующих главах. А сейчас отметим, что под графом Джонсона мы понимаем граф 3(п,г), вершинами которого являются произвольные г—элементные наборы из множества {1 ,...,п}, а ребра соединяют вершины в том и только в том случае, когда две вершины имеют г — 1 общий элемент. В разных приложениях эффективным инструментом применения является обобщение графа Джонсона С(п,г,з). В этом случае ребро устанавливается тогда и только тогда, когда две вершины имеют ровно в общих элементов, где в < г. Заметим, что под словом "элемент" мы можем понимать как число, так и объект произвольной природы, что позволяет использовать граф Джонсона для решения задач различного типа.

Графы Джонсона — являются эффективным инструментом, который применяется в задачах, связанных с комбинаторикой, оптимизацией и анализом данных. Они используются в теории кодирования [1], биоинформатике [2], [3], [4], сетевых технологиях [5],[6], криптографии [7] и других дисциплинах, где рассматриваются подмножества с заданным уровнем пересечений.

В комбинаторике эти графы находят применение при построении блок-дизайнов, которые упорядочивают элементы множества в подмножества с определёнными комбинаторными свойствами. Элементы множества группируются так, чтобы соблюдались определённые условия на пересечения подмножеств.

В теории кодирования графы Джонсона применяются для разработки корректирующих кодов с минимальным расстоянием, которые обеспечивают

устойчивость к ошибкам при передаче данных. Такие коды особенно важны в телекоммуникационных системах, где передача информации подвержена шуму.

Обобщённые графы Джонсона С(п,г,з), задавая уровень пересечения й между вершинами, позволяют эффективнее применять их в ещё более широком спектре задач.

Рассмотрим свойства графа Джонсона и его обобщения. Заметим, что число вершин в графе Джонсона С(п,г,з) определяется формулой Сгп. Значит, степень каждой вершины графа Джонсона С(п,г,з) определяется формулой С® • О—. Таким образом, граф Джонсона является регулярным графом, то есть графом, вершины которого имеют одинаковую степень. Это особенно важно при моделировании равномерных систем, таких как сети связи или распределённые вычислительные системы, где требуется равномерное распределение нагрузки.

Отметим, что граф С(п,г,з) является симметричным графом, то есть для любых двух пар вершин графа (и1,у1) и (и2,у2), таких что и1 смежен с г>1, а и2 смежен с у2 (ребра) существует автоморфизм, который переводит и1 в и2 и г>1 в у2.

Важнейшими характеристиками в теории графов являются кликовое число, число независимости и хроматическое число. Асимптотические свойства этих характеристик мы подробно рассмотрим в следующей главе.

В комбинаторной геометрии значительный интерес представляет проблема Борсука, которая состоит в том, что любое ограниченное множество в ^ можно разбить на й +1 часть меньшего диаметра. Это важно в задачах, связанных с минимизацией конфликтов, оптимизацией сетевых структур и построения эффективных планов. Хотя гипотеза была опровергнута для ё, ^ 64, графы Джонсона С(п,г,з), построенные на г-элементных подмножествах п-элементного множества, могут быть использованы для исследования гипотезы Борсука. Задача сводится к проверке возможности разбиения вершин графа на минимальное число частей, где диаметр каждой части ограничен. Для некоторых графов Джонсона гипотеза Борсука может выполняться, что делает их важным примером для анализа комбинаторных свойств разбиений.

Графы С(п,г,з) также используются в теории Рамсея для построения и анализа экстремальных комбинаторных структур. Они помогают находить оценки чисел Рамсея, так как такие графы обладают регулярностью и позволяют строить примеры, в которых долго не возникает одноцветной клики. В частности, они помогают находить нижние границы чисел Рамсея,

демонстрируя, что для некоторых значений числа Рамсея Я(г, в) требуется больше вершин, чем по другим методикам.

Немаловажным обобщением графа Джонсона С(п,г,з) является его подграф, в котором ребра устанавливаются с некоторой заданной вероятностью р. Такая конструкция называется случайный граф Джонсона Ср(п,г,з). В настоящей работе изучаются асимптотические свойства экстремальных характеристик.

Случайные графы Джонсона также находят применение при решении различных важных задач науки и техники. Среди таких задач можно выделить следующие. Ср(п,г,з) обладают сильными расширяющими свойствами [8], что делает их полезными для построения надёжных коммуникационных сетей, где даже при отказе части узлов информация остаётся доступной. Кроме этого, они применяются при создании случайных семплирующих алгоритмов, применяемых в проверке вероятностных доказательств (например, РСР-теория в криптографии [9]), а также построения надёжных хэш-функций для защиты данных и алгоритмов шифрования, обеспечивая такие свойства, как устойчивость к коллизиям и предобразам [10].

Случайные графы Джонсона полезны в областях, где требуется эффективное распределение ресурсов, устойчивость к сбоям и работа с частично пересекающимися структурами. Они находят применение в криптографии, сетевых вычислениях и машинном обучении.

Все вышеперечисленные приложения подчеркивают актуальность в настоящее время изучения поведения основных характеристик случайных графов Джонсона при различных условиях.

Другим направлением работы являлись задачи оценки хроматического числа различных многообразий. Эти тематика пересекается с вышеперечисленными исследованиями, так как при оценке хроматического числа использовался так называемый графический подход.

В настоящей работе рассматриваются вопросы, связанные с обобщениями задачи Хадвигера-Нельсона [11], в классической постановке которой требуется определить хроматическое число плоскости с запрещенным расстоянием 1, то есть определить в какое минимальное число цветов можно раскрасить точки евклидовой плоскости так, чтобы любые две точки на расстоянии 1 имели разный цвет. Эта классическая проблема не имеет до сих пор решения,

однако известно, что хроматическое число плоскости лежит в диапазоне между 4 и 7 цветами, причем в 2018 году было показано, что в 4 цвета раскрасить плоскость нельзя [12]. Стоит отметить, что естественным подходом к определению границ этого числа является рассмотрение различных разбиений метрического пространства на совокупность непересекающихся множеств, которое называется замощением [13].

По аналогии с этой задачей рассматривались задачи определения хроматического числа различных пространств и многообразий в них. Подобные задачи изучались в дискретных моделях, например, для плотной упаковки в R3, где определение расстояний и оценка хроматического числа позволяют установить границы оценки хроматического числа [14]. В указанной работе рассматриваются графы расстояний, построенные на вершинах трёхмерных решёток плотной упаковки, в частности, fcc-решётки (face-centered cubic). Авторы исследуют хроматические числа таких графов с учётом запрещённого расстояния 1 и приводят численные оценки для различных типов решёток.

В последнее время опубликовано множество работ посвященных поиску хроматического числа различных многообразий с ограничениями на расстояния между точками одного цвета.

Первоначально постановка задачи о раскраске метрического пространства с ограничениями на диаметр односвязных одноцветных областей и минимальным расстоянием между ними была предложена К.Томассеном в [15]. В этой статье рассматривается задача о раскраске плоскости с ограничениями, при которых плоскость разбивается на односвязные области диаметра строго меньше 1, все области являются одноцветными, все пары областей одного цвета находятся на расстоянии больше 1. Основной результат формулируется следующим образом: если поверхность (в том числе плоскость) удовлетворяет трём условиям — (i) не содержит коротких (диаметра менее 2) неконтрактируемых кривых; (ii) всякая замкнутая кривая малого диаметра ограничивает область малой площади; и (iii) сама поверхность имеет достаточно большой диаметр, — то любая раскраска такой поверхности, которая удовлетворяет условиям, требует как минимум семи цветов. Это условие называется условием Томассена или "правильной" раскраской. Подробнее это будет рассмотрено в соответсвующей главе, а пока будем называть раскраску сферы "правильной" ("хорошей"), если она удовлетворяет локальной связности и отсутствию одноцветных пар на расстоянии 1.

К настоящему времени существует большое число работ, посвященных поиску и оценке хроматического числа не только пространств, но и различных многообразий в них, например [12, 13, 15—19].

Начиная с 70-ых годов прошлого века проблему поиска хроматического числа плоскости изучали в работах [20—23]. В 80-ые годы эта проблема была известна как проблема колоризации [19, 24—29]. В 90-ые годы эта проблема стала называться проблемой раскраски расстояний [30, см. 2.18], [31, 32].

Примером поиска хроматического числа многообразия является задача о раскраске двухмерной сферы (поверхности шара) заданного радиуса г при геодезическом расстоянии 1 между точками - то есть раскраска сферы в несколько цветов так, чтобы любые две точки на сфере, лежащие друг от друга на дуге длины 1, были разного цвета. Минимальное число цветов для такой раскраски сферы радиуса г называется хроматическим числом сферы х(^2).

Очевидно, что для сферы с г < 1/2, хроматическое число х(^2) = 1. В свою очередь, если г = 1/2, то одним цветом мы сможем покрыть всю поверхность сферы за исключением одной точки, для которой понадобится 2-ой

цвет, так что х(^2) = 2.

2

К настоящему времени получены следующие результаты, касающиейся хроматического числа сферы. В 1976 году Густавус Симмонс сформулировал гипотезу: если радиус сферы г строго больше 1/2, то любая ее раскраска в 3 цвета непременно содержит две точки одного цвета на расстоянии 1, то есть для сфер радиуса г > 1/2 требуется минимум 4 цвета. Отдельно другим

авторам удалось доказать [33], что при 1/2 < г ^ ^, хроматическое число сферы строго равно 4, и вообще при г > 1/2, х(&г) ^ 4, тем самым полностью доказав гипотезу Симмонса. Это доказательство основано на анализе геометрических свойств трёхцветных раскрасок сферы, конфигураций окружностей единичного радиуса и меры пересечений одноцветных областей. В частности, показано, что при г > 1/2 невозможно покрыть сферу тремя измеримыми множествами без появления единичных хорд внутри одного из них, что завершает исследование нижней оценки хроматического числа в этой области. Точное значение хроматического числа достигается путём явной конструкции корректной четырёхцветной раскраски и анализа невозможности трёхцветного покрытия через геометрическое исследование распределения цветных множеств и их пересечений с единичными окружностями на сфере.

При дальнейших исследованиях был получен ряд уточнений оценок хроматического числа сферы снизу. Например, в той же работе [33] доказано, что при г > \1?3-2^" хроматическое число х(^2(г)) > 4. Для доказательства авторы предполагают существование корректной 4-цветной измеримой раскраски и анализируют геометрию её одноцветных множеств. Рассматривается поведение таких множеств при пересечении с окружностями единичного радиуса, расположенными на сфере. Показывается, что при указанных радиусах никакое из одноцветных множеств не может содержать более одной дуги определённой длины, зависящей от г, и при г > эта длина оказывается строго меньше четверти окружности. Таким образом, четыре такие дуги не могут покрыть всю единичную окружность, что приводит к противоречию с предположением о корректной 4-цветной раскраске всей сферы.

Отдельно было показано [34], что при г = хроматическое число

сферы удовлетворяет неравенству х(^2) ^ 5. Авторы строят конечный граф расстояний, допускающий вложение в сферу данного радиуса, в котором все рёбра соединяют пары точек на расстоянии 1. Комбинаторный анализ показывает, что хроматическое число полученного графа равно 5, то есть его нельзя корректно раскрасить в 4 цвета без появления одноцветного ребра. Так как граф реализуется геометрически на сфере, это даёт немедленное нижнее ограничение на хроматическое число при выбранных значениях радиуса.

Также в [17, 35] показано, что при г = ^ хроматическое число сферы равно четырём, то есть х(^2) = 4. В обеих работах представлена явная конструкция корректной 4-цветной раскраски поверхности сферы с использованием тетраэдральной симметрии, при которой исключается наличие пар точек одного цвета на расстоянии 1. В работе [17] представлена явная 4-цветная раскраска поверхности сферы, исключающая единичное расстояние между точками одного цвета. Построение основано на разбиении сферы с использованием тетраэдральной симметрии: вершины правильного тетраэдра определяют центральные направления, вдоль которых размещаются четыре цветовые области. Геометрический анализ показывает, что при этом никакие две точки одного цвета не могут находиться на расстоянии 1. В случае работы [35] авторы независимо строят 4-цветную раскраску поверхности сферы, в которой отсутствуют одноцветные пары точек на расстоянии 1. Конструкция использует геометрическую упаковку на сфере, задаваемую тетраэдральной

симметрией и анализом расстояний между точками на фиксированных дугах. В отличие от подхода Симмонса, метод авторов опирается на графовую интерпретацию — рассматриваются графы расстояний на сфере, и показано, что хроматическое число соответствующего графа не менее 4. В результате также устанавливается точное значение хроматического числа: = 4.

Однако, интерес также составляет рассмотрение оценок сверху хроматического числа сферы. Рассмотрев обобщение классической задачи Хадвигера-Нельсона на трехмерное евклидово пространсво К3 [36] Д. Кулсон построил корректную 15-цветную раскраску. Конструкция основана на периодическом разбиении пространства на параллелепипеды и последующем окрашивании их с использованием пространственной решётки. Метод гарантирует, что никакие две точки одного цвета не могут находиться на расстоянии 1, откуда следует, что х(К3) ^ 15. В работе [37] приведено уточнение и интерпретация данной оценки. Так как сфера радиуса г > | является подмножеством пространства, где реализуемо расстояние 1, указанная раскраска остаётся корректной и на сфере, что даёт оценку х(^22) ^ 15.

При г ^ — установлено, что хроматическое число сферы не превышает 5, то есть х(^) ^ 5 [17], [38]. В работе [17] приведена явная 5-цветная раскраска сферы для малых радиусов, основанная на размещении цветных областей вдоль направлений правильного многогранника. В [38] результат уточняется и обобщается: автор рассматривает измеримые раскраски и показывает, что при г ^ ^д возможно покрытие сферы пятью измеримыми множествами, при котором отсутствуют одноцветные пары точек на расстоянии 1. При г ^ ^, х(5?) ^ 6 [38]. Таким образом, на текущий момент установлено, что при г > 2 хроматическое число сферы удовлетворяет двойному неравенству 4 < х(5?) < 15, причём точные значения известны лишь для отдельных значений радиуса г.

Отдельно стоящим результатом можно считать работу Т. Сиргедаса [39], в которой показано, что при г ^ 12.44 справедливо неравенство х(^) ^ 7. Построение основано на проецировании гексагональной раскраски плоскости на сферу с помощью центральной проекции. При достаточно большом радиусе такая проекция сохраняет метрические свойства, в частности — отсутствие пар точек одного цвета на расстоянии 1, что обеспечивает корректность 7-цветной раскраски на сфере. Таким образом, в случае достаточно больших радиусов верхняя оценка хроматического числа ограничена значением 7, что представляет собой сферический аналог классической оценки для плоскости.

Стоит отметить, что данный результат получен без использования условия Томассена в определении хроматического числа сферы.

В диссертации проводится исследование, уточняющее оценку хроматического числа сферы разбитой на области с условием, что области находятся на расстоянии больше 1.

Целью данной работы является изучение асимптотических свойств обобщенных графов Джонсона и их случайных подграфов, а также оценки хроматического числа поверхности сферы в обобщенной задаче Хадвигера-Нельсона.

Научная новизна: Все результаты данной диссертации получены автором и являются новыми. В частности, впервые получены асимптотические оценки снизу числа независимости графов Джонсона для р(п) при установленных ограничениях и существенно усилены ограничения на радиус сферы для «правильной» раскраски в 7 цветов.

Результаты, выносимые на защиту:

1. Проведен сравнительный анализ большого числа результатов в области исследования характеристик графов Джонсона и случайных графов Джонсона и систематизированы результаты исследования.

2. Получена новая асимптотическая оценка снизу числа независимости случайного графа Джонсона для р(п) при установленных ограничениях.

3. Доказана новая теорема, являющаяся обобщением известных результатов, устанавливающая асимптотическую оценку снизу числа независимости случайного графа Джонсона при ограничении на характер стремления р(п) ^ 0.

4. Получены ограничения на радиус сферы £2(г) для "правильной" раскраски в 7 цветов.

5. С помощью компьютерного анализа найдена и представлена правильная раскраска квадрата, куба, 4 - степени планарного графа, представляющей собой триангуляцию плоскости с наличием одной вершины степени 5.

Степень достоверности и апробация результатов. Достоверность подтверждена строгими и полностью воспроизводимыми математическими доказательствами, изложенными в диссертации и прошедшими внешнее рецензирование в рейтинговых изданиях. Все вычислительные компоненты доступны в виде репозитория с исходным кодом, что обеспечивает контроль повторяемости результатов.

Основные научные результаты были опубликованы в трех рецензируемых изданиях, три из которых включены в перечень научных журналов, рекомендованных Московским физико-техническим институтом (МФТИ, Физтех). Кроме того, результаты исследований были представлены на международных конференциях и научных семинарах:

1. Конференция "67-я Всероссийская научная конференция МФТИ", 2025, Москва, Россия;

2. Семинар профессора А. М. Райгородского в МФТИ, 2025, Москва, Россия;

3. Семинар "Случайные блуждания, ветвящиеся процессы" в МГУ, 2025, Москва, Россия.

Объем и структура работы. Диссертация состоит из введения, 2 глав и заключения. Полный объём диссертации составляет 128 страниц. Список литературы содержит 179 наименований.

Глава 1. Графы Джонсона 1.1 Основной объект

Одним из классических объектов современной комбинаторики является граф С(п,г,в) = (V(п,г), Е(п,г,в)).

Его вершинами служат все возможные г-элементные подмножества множества = {1,... ,п}, а ребрами две вершины соединяются тогда и только тогда, когда мощность пересечения соответствующих подмножеств равна в. Формально:

V(п,г) = {А сПп : |А| = г}, Е(п,г,в) = {{А,В} : |А П В| = в}.

Разумеется, здесь г ^ п, в ^ г — 1. При й = г — 1 получается граф 3(п,г), называемый в теории кодирования графом Джонсона. При в = 0 возникает не менее известный кнезеровский граф КС(п,г). Тем не менее, в настоящей работе мы будем любой граф С(п,г,з) называть (обобщенным) графом Джонсона. Такое предпочтение обусловлено тем, что граф С(п,г,з) напрямую связан с так называемой схемой Джонсона (см. [1]). Графы Джонсона играют огромную роль в самых разных ключевых разделах дискретного анализа.

Кнезеровские графы. Напомним, что кнезеровским называется граф С(п,г,0). При г = 1 этот граф становится, как нетрудно видеть, полным: С(п,1,0) = Кп (Кп — это стандартное обозначение для полного графа на п вершинах). При 2г > п, напротив, кнезеровский граф не имеет ни одного ребра. Если п четно и 2г = п, то кнезеровский граф состоит из отдельных ребер, т.е. в стандартных терминах теории графов является паросочетанием. Граф С(5,2,0) совпадает с очень известным графом Петерсена (см. рис. 1.1).

Проблема, которую сформулировал в 1955 году М. Кнезер (см. [40]), состояла в отыскании хроматического числа графа С(п,г,0). Напомним, что хроматическое число произвольного графа С = (У,Е) — это наименьшее количество цветов, в которые можно так покрасить все вершины графа, чтобы концы каждого его ребра имели разные цвета. Формально:

х(С) = ш1п{^ : V = Уг и ... и Ук, V г V х,у е V, {х,у} # V}.

Хроматическое число графа — это одна из самых важных его экстремальных характеристик. Фактически она говорит о том, как эффективнее всего кластеризовать объекты из множества V, если мы хотим избежать каких-то "конфликтов" между парами объектов в каждом кластере. В настоящей работе мы в том числе обсуждаем эту характеристику для произвольных графов Джонсона.

Гипотеза, которую высказал сам Кнезер, состояла в том, что х(&(п,г,0)) = п — 2г + 2. Легко видеть, что в простейших случаях, упомянутых выше, гипотеза верна. Необычную историю ее доказательства можно найти в ряде разных источников (см., например, [41], [42], а также пункт 2.3.2 этой главы). Благодаря этой гипотезе был развит новый мощный топологический метод в комбинаторике (см. [42]).

Матрицы Адамара Напомним, что матрицей Адамара называется квадратная матрица размера п х п, в которой все элементы суть ±1 и каждые две строки ортогональны (в смысле равенства нулю евклидова скалярного произведения). Заметим, что в такой матрице ортогональны и столбцы. Из этого следует, что любую матрицу Адамара можно привести к такому виду, в котором ее верхняя строка и левый столбец целиком состоят из единиц. Понятно, стало быть, что каждая строка, кроме первой, у такой матрицы должна содержать ровно половину единиц и половину минус единиц, т.е. при п > 1 размер матрицы обязан быть четным. Более того, если п > 2, то ортогональность любых двух строк (кроме первой) означает, что количество общих единиц в этих строках (и количество их общих минус единиц) равно п/4, т.е. п обязано иметь вид п = 4к. Знаменитая гипотеза Адамара состоит в том, что для любого

п такого вида существует матрица Адамара. Эта гипотеза доказана для многих значений п. В частности, известно, что для любого £ > 0 найдется такое щ, что при всех п ^ щ между п и (1 + £)п есть порядок матрицы Адамара. Тем не менее, в общем случае гипотеза по сей день остается открытой (см., например, [43]). Это удивительно, ведь с геометрической точки зрения речь идет о построении правильного симплекса с п — 1 вершинами в вершинах куба [—1,1]п, которые лежат в гиперплоскости х\ + ... + хп = 0.

Значение матриц Адамара трудно переоценить. Они возникают в теории кодирования, в теории графов, в комбинаторной геометрии и многих других областях математики.

Покажем связь матрицы Адамара с графами Джонсона. Рассмотрим при п = 4к граф G(n,n/2,n/4). Напомним, что кликой в графе называется любой его полный подграф. Размер максимальной (по числу вершин) клики в графе G обозначается w(G) и называется кликовым числом графа. Пусть дана некоторая клика в графе G(n,n/2,n/4). Сопоставим каждой ее вершине А (это подмножество мощности п/2) вектор, в котором на позициях с номерами из А стоят единицы, а на остальных позициях расположены минус единицы. Это типичная строка матрицы Адамара. Если А и В — это две вершины клики, то IA П В | = п/4, а это значит, что соответствующие векторы ортогональны. Иными словами, строки матрицы Адамара с номерами от второго находятся во взаимно однозначном соответствии с вершинами клики графа Джонсона G(n,n/2,n/4). А гипотеза Адамара в этих терминах сводится к утверждению о том, что w(G(n,n/2,n/4)) = п — 1.

Кликовое число графа — это еще одна экстремальная характеристика, которую мы обсудим в случае произвольных графов G(n,r,s). Отметим, что она тесно связана с хроматическим числом, ведь хроматическое число любой клики равно числу ее вершин, а стало быть, x(G) ^ w(G).

Теория Рамсея. Теория Рамсея — это обширнейшая тема, находящаяся в самом центре современных исследований на стыке комбинаторики и computer science. Здесь мы лишь вкратце напомним самые базовые определения. Прежде всего заметим, что в графах бывают не только клики, которые мы обсуждали в предыдущих параграфах, но и "антиклики". Последнее слово взято в кавычки, т.к. по не вполне понятным причинам оно не используется официально, хотя оно и очень удобно. Понятно, что речь идет о графах без ребер. Тем не менее, официальным термином здесь служит выражение независимое множество

вершин. Это такое множество вершин графа, в котором нет ни одного ребра. Аналогом кликового числа является, соответственно, число независимости, которое равно максимуму мощности независимого множества вершин в графе и обозначается <х(С). Отметим, что даже обозначение подчеркивает, что в некотром смысле число независимости и кликовое число противоположны (альфа и омега — это, как известно, первая и последняя буквы греческого алфавита). Другими словами, пусть С — это граф, полученный из графа С удалением всех его ребер и проведением тех ребер, которых в С не было. То есть, С — это дополнение графа С до полного графа Кп. Тогда а(С) = ш(С) и наоборот.

Список литературы диссертационного исследования кандидат наук Синельников-Мурылев Петр Сергеевич, 2025 год

Список литературы

[1] Ф.Дж. Мак-Вильямс и Н.Дж.А. Слоэн. — Теория кодов, исправляющих ошибки. — Москва: Радио и связь, 1979.

[2] S. Akmal and C. Jin. — "Near-Optimal Quantum Algorithms for String Problems". — In: Algorithmica 85.8 (2023), p. 2260—2317.

[3] D. Uminsky et al. — "Detecting Higher Order Genomic Variant Interactions with Spectral Analysis". — In: 2019 27th European Signal Processing Conference (EUSIPCO). — IEEE, 2019, — P. 1—5.

[4] A. Lenz et al. — "Coding over Sets for DNA Storage". — In: IEEE Transactions on Information Theory 66.4 (2019), p. 2331—2351.

[5] А. М. Райгородский. — Модели Интернета. — Долгопрудный: Интеллект, 2013, — С. 104.

[6] A. E. Brouwer, A. M. Cohen, and A. Neumaier. — Distance-Regular Graphs. — Berlin: Springer, 1989.

[7] J. H. van Lint and R. M. Wilson. — A Course in Combinatorics. — 2nd ed. — Cambridge: Cambridge University Press, 2001.

[8] C. Thomas and U. Girish. — Expansion in the Johnson Graph. — Unpublished manuscript. —May 2019. — url: https://clathomasprime. github.io/papers/JohnsonExpansion.pdf.

[9] S. Khot et al. — Small Set Expansion in The Johnson Graph. — Tech. rep. TR18-078. — ECCC Report No. 78, published 23 April 2018. — Electronic Colloquium on Computational Complexity (ECCC), Apr. 2018. — url: https://eccc.weizmann.ac.il/report/2018/078/.

[10] W.-F. Cao et al. — "Constructing quantum Hash functions based on quantum walks on Johnson graphs". — In: Quantum Information Processing 17.7 (2018). Published July 2018; INIS RN: 50026650, p. 1—11.

[11] H. Hadwiger. — „Ein Überdeckungssatz für den Euklidischen Raum". — In: Portugaliae Mathematica 4.3 (1944), S. 140-144.

[12] A. de Grey. — "The chromatic number of the plane is at least 5". — In: Geombinatorics 28.1 (2018), p. 18—31.

[13] A. Soifer. — The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. — Springer, 2009.

[14] N. Gastineau and O. Togni. — "Coloring of the d-th power of the face-centered cubic grid". — In: arXiv preprint arXiv:1806.08136 (2018). — eprint: 1806.08136. — url: https://arxiv.org/abs/1806.08136.

[15] C. Thomassen. — "On the Nelson unit distance coloring problem". — In: The American Mathematical Monthly 106.9 (1999), p. 850—853.

[16] N.G. de Bruijn and P. Erdos. — "A colour problem for infinite graphs and a problem in the theory of relations". — In: Proc. Koninklijke Nederlandse Akademie van Wetenschappen, Ser. A 54 (1951), p. 371—373.

[17] G.J. Simmons. — "The chromatic number of the sphere". — In: Journal of the Australian Mathematical Society, Series A 21.4 (1976), p. 473—480.

[18] A.M. Raigorodskii. — "Cliques and cycles in distance graphs and graphs of diameters". — In: Contemporary Mathematics 625 (2014), p. 93—109.

[19] M. Gionfriddo. — «A short survey on some generalized colourings of graphs». — In: Ars Combinatoria 24B (1987), pp. 155-163.

[20] F. Kramer et H. Kramer. — « Un problème de coloration des sommets d'un graphe ». — In : Comptes Rendus de l'Académie des Sciences de Paris, Série A 268 (1969), p. 46-48.

[21] F. Speranza. — «Colorazioni di specie superiore d'un grafo». — In: Bollettino dell'Unione Matematica Italiana. Serie 4 12 (1975), pp. 53-62.

[22] G. Wegner. — Graphs with given diameter and a colouring problem. — Technical Report. — University of Dortmund, 1977.

[23] S. Antonucci. — «Generalizzazioni del concetto di cromatismo d'un grafo». — In: Bollettino dell'Unione Matematica Italiana. Serie 5 15-B (1978), pp. 20-31.

[24] M. Gionfriddo. — «Sulle colorazioni Ls d'un grafo finito». — In: Bollettino dell'Unione Matematica Italiana. Serie 5 15-A (1978), pp. 444-454.

[25] M. Gionfriddo. — «Alcuni risultati relativi alle colorazioni Ls d'un grafo». — In: Rivista di Matematica della Université di Parma, Serie 4 6 (1980), pp. 125-133.

[26] M. Gionfriddo. — «Su un problema relativo alle colorazioni L2 d'un grafo planare e colorazioni Ls». — In: Rivista di Matematica della Université di Parma, Serie 4 6 (1980), pp. 151-160.

[27] M. Gionfriddo. — «Un teorema sul numero s-cromatico di un grafo». — In: Atti della Società Peloritana dei Pericolanti. Classe di Scienze Fisiche, Matematiche e Naturali XXVI (1980), pp. 225-232.

[28] M. Gionfriddo. — «Sul parametro s(G) d'un grafo Ls-colorabile e problemi relativi». — In: Rivista di Matematica della Université di Parma, Serie 4 8 (1982), pp. 1-7.

[29] M. Gionfriddo. — «Colorazioni generalizzate di un grafo—recenti risultati e probleme aperti». — In: Atti del settimo convegno A.M.A.S.E.S., Acireale, 16-18 giugno. — 1983, — Pp. 199-213.

[30] T. R. Jensen and B. Toft. — Graph Coloring Problems. — New York: Wiley, 1995.

[31] S. A. Wong. — "Colouring graphs with respect to distance". — M.Sc. Thesis. Ontario, Canada: University of Waterloo, Department of Combinatorics and Optimization, 1996.

[32] J. van den Heuvel and S. McGuinness. — "Colouring the square of a planar graph". — In: Journal of Graph Theory 42 (2003), p. 110—124.

[33] D. Cherkashin and V. Voronov. — "On the Chromatic Number of 2-Dimensional Spheres". — In: Discrete & Computational Geometry 71 (2024), p. 467—479. — url: https://doi.org/10.1007/s00454-023-00483-3.

[34] V.A. Voronov, A.M. Neopryatnaya, and E.A. Dergachev. — "Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres". — In: Discrete Mathematics 345.12 (2022), p. 113106.

[35] C.D. Godsil and J. Zaks. — "Colouring the sphere". — In: arXiv preprint (2012). — eprint: 1201.0486. — url: https://arxiv.org/abs/1201.0486.

[36] D.A. Coulson. — "15-colouring of 3-space omitting distance one". — In: Discrete Mathematics 256.1-2 (2002), p. 83—90. — url: https://doi.org/ 10.1016/S0012-365X(01)00466-0.

[37] R. Radoicic and G. Toth. — "Note on the chromatic number of the space". — In: Discrete and Computational Geometry. — Vol. 25. — Algorithms and Combinatorics. — Berlin: Springer, 2003, — P. 695—698.

[38] G. Malen. — "Measurable colorings of -S^". — In: Geombinatorics 24.4 (2015), p. 172—180.

[39] T. Sirgedas. — "The surface of a sufficiently large sphere has chromatic number at most 7". — In: Geombinatorics 30.3 (2021), p. 138—151.

[40] M. Kneser. — „Aufgabe 360". — In: Jahresbericht der Deutschen Mathematiker-Vereinigung 2 (1956), S. 27.

[41] А.М. Райгородский. — Гипотеза Кнезера и топологические методы в комбинаторике. — Москва: МЦНМО, 2011.

[42] J. Matousek. — Using the Borsuk-Ulam theorem. — Universitext. — Berlin: Springer, 2003.

[43] М. Холл. — Комбинаторика. — Москва: Мир, 1970.

[44] P. Erdos and G. Szekeres. — "A combinatorial problem in geometry". — In: Compositio Mathematica 2 (1935), p. 463—470.

[45] S. Radziszowski. —"Small Ramsey Numbers". — In: The Electronic Journal of Combinatorics (2023). Accessed: 30.09.2025. — url: https://www. combinatorics.org/ojs/index.php/eljc/article/view/21.

[46] R.L. Graham, B.L. Rothschild, and J.H. Spencer. — Ramsey theory. — Second. — New York: John Wiley and Sons, 1990.

[47] M. Campos et al. — "An exponential improvement for diagonal Ramsey". — In: arXiv (2023). Accessed: 30.09.2025. — eprint: 2303.09521. — url: https://arxiv.org/abs/2303.09521.

[48] P. Gupta et al. — "Optimizing the CGMS upper bound on Ramsey numbers". — In: arXiv (2024). Accessed: 30.09.2025. — eprint: 2407. 19026. — url: https://arxiv.org/abs/2407.19026.

[49] P. Balister et al. — "Upper bounds for multicolour Ramsey numbers". — In: arXiv (2024). Accessed: 30.09.2025. — eprint: 2410.17197. — url: https://arxiv.org/abs/2410.17197.

[50] N. Alon and J.H. Spencer. — The Probabilistic Method. — 4th ed. — Hoboken, NJ: John Wiley and Sons, 2015.

[51] А.М. Райгородский. — Линейно-алгебраический метод в комбинаторике. — 2-е изд. — Москва: МЦНМО, 2015.

[52] А.М. Райгородский. — «Проблема Борсука и хроматические числа некоторых метрических пространств». — В: Успехи мат. наук 56.1 (2001), с. 107—146.

[53] A.M. Raigorodskii. — "Coloring Distance Graphs and Graphs of Diameters". — In: Thirty Essays on Geometric Graph Theory. — Ed. by J. Pach. — Springer, 2013, — P. 429—460.

[54] A.M. Raigorodskii. — "Cliques and cycles in distance graphs and graphs of diameters". — In: Discrete Geometry and Algebraic Combinatorics 625 (2014), p. 93—109.

[55] P. Brass, W. Moser, and J. Pach. — Research Problems in Discrete Geometry. — Berlin: Springer, 2005.

[56] A. Soifer. — The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. — New York: Springer, 2009.

[57] V.G. Boltyanski, H. Martini, and P.S. Soltan. — Excursions into Combinatorial Geometry. — Universitext. — Berlin: Springer, 1997.

[58] D.G. Larman and C.A. Rogers. — "The realization of distances within sets in Euclidean space". — In: Mathematika 19 (1972), p. 1—24.

[59] R. Prosanov. — "A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space". — In: Discrete Applied Mathematics 276 (2020), p. 115—120.

[60] N.G. de Bruijn and P. Erdos. — "A colour problem for infinite graphs and a problem in the theory of relations". — In: Proc. Koninkl. Nederl. Acad. Wet, Ser. A 54.5 (1951), p. 371—373.

[61] P. Shuldiner and R. Wayne. —"The Clique Structure of Johnson Graphs". — In: arXiv (2022). Accessed: 30.09.2025. — eprint: 2208.12710. — url: https://arxiv.org/abs/2208.12710.

[62] А.С. Гусев. — «Кликовые числа случайных подграфов некоторых дистанционных графов». — В: Проблемы передачи информации 54.2 (2018), с. 73—85.

[63] Ф. Харари. — Теория графов. — УРСС, 2003.

[64] Ch.J. Colbourn and J.H. Dinitz. — Handbook of Combinatorial Designs. — Second. — Boca Raton: Chapman and Hall/CRC, 2007.

[65] P. Keevash. —"The existence of designs". —In: arXiv (2014). Accessed: 30.09.2025. — eprint: 1401.3665. — url: https://arxiv.org/abs/1401.3665.

[66] P. Keevash. —"The existence of designs II". — In: arXiv (2018). Accessed: 30.09.2025. — eprint: 1802.05900. — url: https://arxiv.org/abs/1802. 05900.

[67] V. Rodl. — "On a packing and covering problem". — In: European Journal of Combinatorics 6 (1985), p. 69—78.

[68] P. Frankl and Z. Furedi. —"Forbidding just one intersection". —In: Journal of Combinatorial Theory, Series A 39.2 (1985), p. 160—176.

[69] P. Frankl and R. Wilson. — "Intersection theorems with geometric consequences". — In: Combinatorica 1 (1981), p. 357—368.

[70] Z. Nagy. — "A certain constructive estimate of the Ramsey number". — In: Matematikai Lapok 23.301-302 (1972), p. 26.

[71] P. Erdos, Ch. Ko, and R. Rado. — "Intersection theorems for systems of finite sets". — In: J. Math. Oxford, Sec. 12.48 (1961).

[72] P. Keevash, D. Mubayi, and R.M. Wilson. —"Set systems with no singleton intersection". — In: SIAM Journal on Discrete Mathematics 20.4 (2006), p. 1031—1041.

[73] Л.И. Боголюбский и А.М. Райгородский. — «Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками 1\ и 12». — В: Матем. заметки 105.2 (2019), с. 187—213.

[74] A. Passuello. — "Semidefinite programming in combinatorial optimization with applications to coding theory and geometry". — NNT: 2013B0R15007, tel-00948055. — PhD thesis. Université Sciences et Technologies - Bordeaux I, 2013.

[75] R. Ahlswede and L.H. Khachatrian. — "The complete intersection theorem for systems of finite sets". — In: Europ. J. Combin. 18 (1997), p. 125—136.

[76] P. Frankl. — "The Erdos-Ko-Rado Theorem is true for n = сkH\ — In: Coll. Soc. Math. J. Bolyai. — Vol. 11. — 1978, — P. 365—375.

[77] R.M. Wilson. — "The exact bound on the Erdos-Ko-Rado Theorem". — In: Combinatorica 4 (1984), p. 247—257.

[78] N.N. Kuzjurin. — "On the difference between asymptotically good packings and coverings". — In: European Journal of Combinatorics 16.1 (1995), p. 35—40.

[79] R.C. Baker, G. Harman, and J. Pintz. —"The difference between consecutive primes, II". —In: Proceedings of the London Mathematical Society 83 (2001), p. 532—562.

[80] D. Ellis, N. Keller, and N. Lifshitz. —"Stability for the complete intersection theorem, and the forbidden intersection problem of Erdos and Sos". — In: Journal of the European Mathematical Society 26.5 (2024), p. 1611—1654.

[81] N. Keller and N. Lifshitz. — "The junta method for hypergraphs and the Erdos-Chvatal simplex conjecture". — In: Advances in Mathematics 392 (2021), p. 107991.

[82] A. Kupavskii and D. Zakharov. — "Spread approximations for forbidden intersections problems". — In: Advances in Mathematics 445 (2024), p. 109653.

[83] D. Cherkashin. — "On set systems without singleton intersections". — In: Discrete Math. Lett. 14 (2024), p. 85—88.

[84] Е.И. Пономаренко и А.М. Райгородский. — «Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения». — В: Проблемы передачи информации 49.4 (2013), с. 98—104.

[85] A. Kupavskii, A. Sagdeev, and D. Zakharov. — "Cutting corners". — In: arXiv (2022). Accessed: 30.09.2025. — eprint: 2211.17150. — url: https: //arxiv.org/abs/2211.17150.

[86] А.М. Райгородский и А.А. Сагдеев. — «Об одной оценке в экстремальной комбинаторике». — В: Доклады РАН 478.3 (2018), с. 271—273.

[87] А.В. Бобу, А.Э. Куприянов и А.М. Райгородский. — «Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением». — В: Матем. сборник 207.5 (2016), с. 17—42.

[88] P. Frankl and V. Rodl. — "Forbidden intersections". — In: Trans. Amer. Math. Soc. 300.1 (1987), p. 259—286.

[89] А.Е. Звонарёв и др. — «О хроматическом числе пространства с запрещенным равносторонним треугольником». — В: Матем. сборник 205.9 (2014), с. 97—120.

[90] А.Е. Звонарёв и А.М. Райгородский. — «Улучшения теоремы Франкла-Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником». — В: Труды Математического Института имени В.А. Стеклова 288 (2015), с. 109—119.

[91] А.А. Сагдеев. — «Улучшенная теорема Франкла-Рёдля и некоторые ее геометрические следствия». — В: Пробл. передачи информ. 54.2 (2018), с. 45—72.

[92] А.А. Сагдеев. — «О теореме Франкла-Рэдла». — В: Изв. РАН. Сер. матем. 82.6 (2018), с. 128—157.

[93] А.А. Сагдеев. — «Об одной теореме Франкла-Уилсона». — В: Пробл. передачи информ. 55.4 (2019), с. 86—106.

[94] P. Keevash and E. Long. — "Frankl-Rodl-type theorems for codes and permutations". — In: Trans. Amer. Math. Soc. 369 (2017), p. 1147—1162.

[95] T. Etzion and S. Bitan. — "On the chromatic number, colorings, and codes of the Johnson graph". — In: Discr. Applied Math. 70 (1996), p. 163—175.

[96] A.E. Brouwer and T. Etzion. — "Some new distance-4 constant weight codes". — In: Advances in Mathematics of Communications 5 (2011), p. 417—424.

[97] Д. Карпов. — Теория графов. — МЦНМО, 2022.

[98] А.М. Райгородский. — «Еще немного о математике раскрасок». — В: Матем. просвещение 31 (2023), с. 55—73.

[99] А.М. Райгородский. — «Проблемы Борсука и Грюнбаума для решетчатых многогранников». — В: Известия РАН 69.3 (2005), с. 81—108.

[100] А.М. Райгородский. — Системы общих представителей в комбинаторике и их приложения в геометрии. — Москва: МЦНМО, 2023.

[101] Д. Цветкович, М. Дуб и Х. Захс. — Спектры графов. Теория и применение. — Киев: Наукова думка, 1984.

[102] А.Э. Гутерман и др. — «О числах независимости дистанционных графов с вершинами в {—1,0,1}п: оценки, гипотезы и приложения к проблемам Нельсона-Эрдеша-Хадвигера и Борсука». — В: Итоги науки и техники. Серия "Современная математика" 65 (2009), с. 82—100.

[103] А.В. Бобу, О.А. Костина и А.Э. Куприянов. — «Числа независимости и хроматические числа некоторых дистанционных графов». — В: Пробл. передачи информ. 51.2 (2015), с. 86—98.

[104] J. Balogh, D. Cherkashin, and S. Kiselev. —"Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs". — In: European J. Combin. 79 (2019), p. 228—236.

[105] G.M. Ziegler. — "Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions". — In: Lect. Notes Comput. Sci. 2122 (2001), p. 159—171.

[106] A.B. Kupavskiy and A.M. Raigorodskii. — "On the chromatic number of R9". — In: J. of Math. Sci. 163.6 (2009), p. 720—731.

[107] A. Sidorenko. — "What we know and what we do not know about Turan numbers". — In: Graphs and Combin. 11 (1995), p. 179—199.

[108] O. Pikhurko. — "Constructions of Turan systems that are tight up to a multiplicative constant". — In: arXiv (2024). Accessed: 30.09.2025. — eprint: 2406.07443. — url: https://arxiv.org/abs/2406.07443.

[109] J. Balogh, A.V. Kostochka, and A.M. Raigorodskii. —"Coloring some finite sets in Rn". — In: Discussiones Mathematicae Graph Theory 33.1 (2013), p. 25—31.

[110] Материалы Московской математической олимпиады. — стр. 4. Accessed: 30.09.2025. — 2012. — url: https://olympiads.mccme.ru/mmo/ 2012/75mmo.pdf.

[111] D. Zakharov. —"Chromatic numbers of Kneser-type graphs". —In: Journal of Combinatorial Theory, Series A 172 (2020), p. 105188.

[112] Д.А. Захаров. — «О хроматических числах некоторых дистанционных графов». — В: Матем. заметки 107.2 (2020), с. 210—220.

[113] B. Bollobas. — Random Graphs. — Second. — Cambridge Univ. Press, 2001.

[114] S. Janson, T. Luczak, and A. Rucinski. — Random Graphs. — New York: Wiley, 2000.

[115] A. Frieze and M. Karonski. — Introduction to Random Graphs. — Cambridge University Press, 2016.

[116] В.Ф. Колчин. — Случайные графы. — Москва: Физматлит, 2002.

[117] R. Durrett. — Random Graph Dynamics. — Cambridge Univ. Press, 2006.

[118] R. van der Hofstad. — Random Graphs and Complex Networks. — Cambridge University Press, 2016.

[119] А.М. Райгородский. — Модели интернета. — Долгопрудный: Интеллект, 2019.

[120] А.М. Райгородский. — Модели случайных графов. — Москва: МЦНМО, 2025.

[121] P. Erdos and A. Renyi. — "On random graphs I". — In: Publ. Math. Debrecen 6 (1959), p. 290—297.

[122] P. Erdos and A. Renyi. — "On the evolution of random graphs". — In: Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), p. 17—61.

[123] P. Erdos and A. Renyi. — "On the evolution of random graphs". — In: Bull. Inst. Int. Statist. Tokyo 38 (1961), p. 343—347.

[124] M. Krivelevich and B. Sudakov. — "Pseudo-random Graphs". — In: More Sets, Graphs and Numbers. — Ed. by E. Gyori et al. — Vol. 15. — Bolyai Society Mathematical Studies. — Berlin, Heidelberg: Springer, 2006.

[125] Ю.Д. Буртин. — «О вероятности связности случайного подграфа n-мерного куба». — В: Пробл. передачи информ. 13.2 (1977), с. 90—95.

[126] Л.И. Боголюбский и др. — «Числа независимости и хроматические числа случайных подграфов в некоторых последовательностях графов». — В: Доклады РАН 457.4 (2014), с. 383—387.

[127] Л.И. Боголюбский и др. — «Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов». — В: Математический сборник 206.10 (2015), с. 3—36.

[128] М.Е. Жуковский и А.М. Райгородский. — «Случайные графы: модели и предельные характеристики». — В: Успехи матем. наук 70.1 (2015), с. 35—88.

[129] А.Р. Ярмухаметов. — «Гигантская и мелкие компоненты в случайных дистанционных графах специального вида». — В: Матем. заметки 92.6 (2012), с. 949—953.

[130] M. Koshelev. —"Spectrum of Johnson graphs". — In: Discrete Mathematics 346.3 (2023), p. 113262.

[131] B. Bollobas and P. Erdos. — "Cliques in random graphs". — In: Mathematical Proceedings of the Cambridge Philosophical Society. — Vol. 80. — 3. — Cambridge University Press, 1976, — P. 419—427.

[132] D. Matula. — "On complete subgraphs of a random graph". — In: Proceedings of the Second Chapel Hill Conference on Combinatory Mathematics and its Applications. — University of North Carolina at Chapel Hill, 1970, — P. 356—369.

[133] A. Frieze. — "On the independence number of random graphs". — In: Discrete Mathematics 81.2 (1990), p. 171—175.

[134] V. Dani and C. Moore. — "Independent sets in random graphs from the weighted second moment method". — In: Lecture Notes in Computer Science: Approximation, Randomization and Combinatorial Optimization. — Vol. 6845. — Springer, 2011, — P. 472—482.

[135] T. Bohman and J. Hofstad. — "Two-Point Concentration of the Independence Number of the Random Graph". — In: arXiv (2022). Accessed: 30.09.2025. — eprint: 2208.00117. — url: https: //arxiv. org/abs/2208.00117.

[136] М.М. Пядёркин. — «О пороговой вероятности для устойчивости независимых множеств в дистанционном графе». — В: Матем. заметки 106.2 (2019), с. 280—294.

[137] A.J.W. Hilton and E.C. Milner. — "Some intersection theorems for systems of finite sets". — In: Quart. J. Math. Oxford Ser. (2) 18 (1967), p. 369—384.

[138] P. Frankl. — "On intersecting families of finite sets". — In: Journal of Combinatorial Theory Ser. A 24 (1978), p. 146—161.

[139] P. Frankl. — "A simple proof of the Hilton-Milner theorem". — In: Mosc. J. Comb. Number Theory 8.2 (2019), p. 97—101.

[140] J. Balogh, T. Bohman, and D. Mubayi. — "Erdos-Ko-Rado in random hypergraphs". — In: Combin. Probab. Comput. 18.5 (2009), p. 629—646.

[141] B. Bollobas, B.P. Narayanan, and A.M. Raigorodskii. — "On the stability of the Erdos-Ko-Rado theorem". — In: J. Combin. Theory Ser. A 137 (2016), p. 64—78.

[142] J. Balogh, R.A. Krueger, and H. Luo. — "Sharp threshold for the Erdos-Ko-Rado theorem". — In: Random Structures and Algorithms 62.1

(2023), p. 3—28.

[143] M.M. Pyaderkin. — "On the stability of some Erdos-Ko-Rado type results". — In: Discrete Mathematics 340.4 (2017), p. 822—831.

[144] Ф.А. Пушняков. — «О количествах ребер в порожденных подграфах некоторых дистанционных графов». — В: Матем. заметки 105.4 (2019), с. 592—602.

[145] Н.А. Дубинин и др. — «Нижние и верхние оценки минимального числа ребер в некоторых подграфах графа Джонсона». — В: Матем. сб. 215.5

(2024), с. 71—95.

[146] Н.М. Деревянко и С.Г. Киселев. — «Числа независимости случайных подграфов некоторого дистанционного графа». — В: Проблемы передачи информации 53.3 (2017), с. 3—14.

[147] М.М. Пядёркин. — «Числа независимости случайных подграфов некоторого дистанционного графа». — В: Матем. заметки 99.2 (2016), с. 288—297.

[148] M. Krivelevich et al. — "On the probability of independent sets in random graphs". — In: Random Structures and Algorithms 22.1 (2003), p. 1—14.

[149] А.М. Райгородский. — «Об одной "олимпиадной" задаче про графы». — В: Квант 2 (2017), с. 2—8.

[150] А.М. Райгородский. — «Об устойчивости числа независимости случайного подграфа». — В: Доклады РАН 477.6 (2017), с. 649—651.

[151] E. Surya and L. Warnke. — "On the concentration of the chromatic number of random graphs". — In: The Electronic Journal of Combinatorics 31.1 (2024), P1.44.

[152] А.С. Гусев. — «Новая верхняя оценка хроматического числа случайного подграфа дистанционного графа». — В: Математические заметки 87.3 (2015), с. 342—349.

[153] M.M. Pyaderkin. — "On the chromatic number of random subgraphs of a certain distance graph". — In: Discrete Applied Mathematics 267 (2019), p. 209—214.

[154] S. Kiselev and A. Raigorodskii. — "On the chromatic number of a random subgraph of the Kneser graph". — In: Doklady Mathematics 96.2 (2017), p. 475—476.

[155] A. Kupavskii. — "On random subgraphs of Kneser and Schrijver graphs". — In: Journal of Combinatorial Theory, Series A 141 (2016), p. 8—15.

[156] M. Alishahi and H. Hajiabolhassan. — "Chromatic Number of Random Kneser Hypergraphs". — In: Journal of Combinatorial Theory, Series A 154 (2018), p. 1—20.

[157] A. Kupavskii. — "Random Kneser graphs and hypergraphs". — In: The Electronic Journal of Combinatorics (2018), P4—52.

[158] S. Kiselev and A. Kupavskii. — "Sharp bounds for the chromatic number of random Kneser graphs". — In: Journal of Combinatorial Theory, Series B 157 (2022), p. 96—122.

[159] P. Erdos. — "Graph theory and probability". — In: Canad. J. Math. 11 (1959), p. 34—38.

[160] А.М. Райгородский. — «Графы с большим хроматическим числом и большим обхватом». — В: Матем. просвещение 20 (2016), с. 228—237.

[161] А.М. Райгородский. — «О дистанционных графах, имеющих большое хроматическое число, но не содержащих больших симплексов». — В: Успехи мат. наук 62.6 (2007), с. 187—188.

[162] Е.Е. Демёхин, А.М. Райгородский и О.И. Рубанов. — «Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера». — В: Матем. сборник 204.4 (2013), с. 49—78.

[163] А.А. Сагдеев. — «О нижних оценках хроматических чисел дистанционных графов с большим обхватом». — В: Матем. заметки 101.3 (2017), с. 430—445.

[164] Р.И. Просанов. — «Контрпримеры к гипотезе Борсука, имеющие большой обхват». — В: Матем. заметки 105.6 (2019), с. 890—898.

[165] А.Б. Купавский. — «Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами». — В: Изв. РАН. Сер. матем. 78.1 (2014), с. 65—98.

[166] M. Bucic and J. Davies. — "Geometric graphs with exponential chromatic number and arbitrary girth". — In: arXiv (2023). Accessed: 30.09.2025. — eprint: 2312.06898. — url: https://arxiv.org/abs/2312.06898.

[167] А.М. Райгородский и К.А. Михайлов. — «О числах Рамсея для полных дистанционных графов с вершинами в {0,1}п». — В: Матем. сборник 200.12 (2009), с. 63—80.

[168] А.М. Райгородский и В.С. Карась. — «О числах Рамсея для произвольных последовательностей графов». — В: Доклады РАН 502 (2022), с. 19—22.

[169] А.М. Райгородский. — «Об одной серии задач рамсеевского типа в комбинаторной геометрии». — В: Доклады РАН 413.2 (2007), с. 171—173.

[170] А.М. Райгородский и М.В. Титова. — «О дистанционных подграфах графов в пространствах малой размерности». — В: Итоги науки и техники. Серия "Современная математика" XX (2011), с. 75—83.

[171] A.B. Kupavskiy, A.M. Raigorodskii, and M.V. Titova. — "New bounds for the distance Ramsey number". — In: Discrete Mathematics 313.22 (2013), p. 2566—2574.

[172] N. Alon and A. Kupavskii. — "Two notions of unit distance graphs". — In: The Seventh European Conference on Combinatorics, Graph Theory and Applications. — Vol. 16. — CRM Series. — 2013, — P. 105—110.

[173] P. Erdos and R.L. Graham. — "Problem proposed at the 6th Hungarian Combinatorial Conference". — In: Abstracts of the 6th Hungarian Combinatorial Conf. (Eger). — July 1981. — Eger, 1981.

[174] А.М. Райгородский. — «О хроматических числах сфер в евклидовых пространствах». — В: Доклады Академии наук 432.2 (2010), с. 174—177.

[175] A.M. Raigorodskii. — "On the chromatic numbers of spheres in Rn". — In: Combinatorica 32.1 (2012), p. 111—123.

[176] А.М. Райгородский. — «К одной теореме Ловаса о хроматическом числе сферы». — В: Математические заметки 98.3 (2015), с. 470—471.

[177] J. Chybowska-Sokol, K. Junosza-Szaniawski, and K. W^sek. — "Coloring distance graphs on the plane". — In: arXiv preprint (2022). — arXiv: 2201.04499.

[178] P. Agoston. — "A lower bound on the number of colours needed to nicely colour a sphere". — In: arXiv preprint arXiv:2404 14398 (2024). — url: https://arxiv.org/abs/2404.14398.

[179] K. Appel and W. Haken. — "Every planar map is four colorable". — In: Illinois J. Math. (Four-Color Theorem preprints). — Series of technical reports. — 1976.

ПРИЛОЖЕНИЕ А ТЕКСТ ПРОГРАММЫ

В данном приложении приведены ключевые фрагменты кода, реализующие алгоритмы построения графов и проверки их хроматических свойств. Каждый листинг снабжён кратким комментарием о назначении блока.

Перед началом работы производится установка и сборка SAT-решателя kissat, необходимого для проверки выполнимости булевых формул.

Листинг 1: Установка и сборка SAT-решателя kissat

!git clone https://github.com/arminbiere/kissat.git %cd kissat ! ./conf igure !make > null %cd . .

!cp kissat/build/kissat kissatl

Следующий фрагмент содержит палитру цветов, используемую для визуализации вершин графов.

Листинг 2: Определение палитры цветов

colors = ['#000000'#FF0000#00FF00#0000FF '#FFFF00' , '#FF00FF ' , '#FF6347 ' , '#DCDCDC' , '#800080' , '#CD5C5C ' , '#D2691E ' , '#191970' ,'#008000' , '#696969' ,'#ADD8E6' , ' #0 08080 ' , '#808000' ,'#FFFFFF' , '#800000' ,'#FF1493' I

Данный фрагмент формирует CNF-представление задачи раскраски графа.

Листинг 3: Формирование булевой формулы (CNF)

import matplotlib.pyplot as plt import networkx as nx from numba import jit

@jit

def int_list_str (lst) : s = " "

for p in lst:

s += str(p) + " " 10 s += " 0\n"

return s

20

25

@jit

def edgelist_to_cnf (el , nvert , ncol): cnf = []

cnf.append(int_list_str([el [0] [0]*ncol + 1])) cnf.append(int_list_str([el [0] [1]*ncol+2])) for u , v in el :

for c in range(1, ncol+1) :

cnf.append(f"-{u*ncol+c} -{v*ncol+c} 0\n") for u in range(nvert):

cnf.append(int_list_str(list(range(u*ncol+1, u*ncol+ncol +1)))) m = len(cnf)

cnf = [f"p cnf {nvert*ncol} {m}\n"] + cnf return cnf

Здесь реализована SAT-проверка: создаётся CNF, запускается решатель и проверяется результат.

Листинг 4: SAT-проверка корректности раскраски

def coloring(el, ncol, timer=3600): nvert = max(map(max, el)) + 1 with open (' test . cnf ' , 'w') as f:

for line in edgelist_to_cnf (el , nvert, ncol): f.write(line)

ans = !timeout $timer ./kissatl test.cnf | grep "c exit **" if not ans :

return 'timeout' if 'exit 10' in ans [0] : 10 return True

if ' exit 20 ' in ans [0] :

return False return 'unknown'

15

def coloringl(el,ncol,timer=3600): # проверка наличия раскраск и с ограничением времени nvert = max(map(max, el)) + 1 with open ('test . cnf','w ') as f:

for line in edgelist_to_cnf(numba.typed.List(el),nvert, nc o l ) :

f.write(line) !timeout $timer ./kissatl test.cnf > coloring.txt with open('coloring.txt','r ') as f: txt = f.read ()

if (txt.find('exit 10')>0) : return True 25 if (txt.find('exit 20')>0) :

return False return 'unknown'

def read_coloring(filename, ncol): 30 with open(filename,'r') as f:

lines = f.readlines() res = {} for l in lines: if l [0] =='v ' : 35 cur = l.split ()

for i in range(1,len(cur)) :

if (cur [i] .strip ()! = ' ') and (cur[i] [0] ! = '-') : lit = int ( cur [i] ) if lit = = 0: 40 continue

k = (lit-1)//ncol if not k in res:

res [k] = (lit -1) % ncol

return res

Функция для нахождения минимального количества цветов, при котором граф можно раскрасить.

Листинг 5: Определение хроматического числа графа

def chrnum(el, cmin=2, cmax=10): for c in range(cmin, cmax+1): res = coloring(el, c) if res == 'timeout':

return res if res is True: return c return cmax * 10

Визуализация графа и окрашивание вершин по найденной раскраске.

Листинг 6: Визуализация раскраски графа

def plot_graph(el, A, dcol, pos=None): n = A.shape [0]

col = [colors [dcol [i] ] for i in range (n)] plt.figure(figsize=(25, 20)) g = nx.Graph(el)

10

15

nx.draw_networkx(g, node_size=150, node_color=col, with_labels=False, pos=A)

Проверка, допускает ли квадрат графа 7-раскраску.

Листинг 7: Проверка 7-раскрашиваемости квадрата графа

def check_sq(G) :

G2 = nx . power (G , 2)

if max(nx.greedy_color(G2).values()) < 7:

return True el = list(G2.edges()) return coloring(el, 7)

Добавление вершин в граф с контролем степени.

Листинг 8: Добавление вершин к графу с заданной степенью

def complete_vert(G , brd , v, d) : G1 = G.subgraph(G [v])

xx = list(set(brd) & set(list(G1.nodes ()))) d0 = len(G1.nodes()) n0 = max(G.nodes()) k = n0 + 1 res = [] prev = xx [0] while k - n0 <= d - d0 : res.append(k) G.add_edge(k, v) G.add_edge(k, prev) prev = k k += 1 G.add_edge(prev , xx [1]) return res

Основной рекурсивный алгоритм построения графов с анализом x(G2).

Листинг 9: Рекурсивная генерация графов с анализом х( G2)

def rec_search_edge(G, vi, cyc, sig = [], f = None): cyc1 = cyc. copy () cyc_len = len(cyc) global nn nn += 1

if nn % 100 == 0:

print(nn) n5l = 0 k=0

5

5

15

20

25

30

35

40

while G.degree(cyc [k]) == 5 and k < cyc_len: k -= 1 n5l += 1 n5r = 0 k = 1

while G.degree(cyc [k]) == 5 and k < cyc_len: k += 1 n5r += 1 max_vi = 0

for n_left in range(n5l+1, 5): for n_right in range(n5r+1, 5):

if n_left + n_right <= min(4, len(cyc)): G1 = G.copy ()

for k in range(-n_left+ 1 , n_right + 1):

G1 . add_edge(cyc[k] , vi) if check_sq(G1):

if n_left + n_right == len(cyc): max_vi = max(max_vi , vi) if vi == 15:

print(nx.to_edgelist(G1)) cyc1 = cyc [n_right :-n_left] + [cyc [-n_left] , cyc [-n_left +1] , vi]

if vi < 30:

max_vi = max(max_vi , rec_search_edge(G1 , vi + 1,

cyc1))

else:

print(n_left , n_right , cyc1) nx.draw (G1) plt.show () else:

if f :

f.write(f'chi(G~2)>7: ({len(G1.nodes())},{len( G1.edges())}) , cyc = {cyc}, {n_left}, {n_right}\n ') else:

print(f'chi(G~2)>7: ({len(G1.nodes())},{len(G1 .edges())}), cyc = {cyc}, {n_left}, {n_right}') return max vi

ПРИЛОЖЕНИЕ Б КОНФИГУРАЦИИ РАСКРАСОК

Рисунок Б.1 — Локальная конфигурация {3} на плоскости

Рисунок Б.2 — Локальная конфигурация {3} на плоскости

Рисунок Б.3 — Локальные конфигурации {5,5} и {4,4} на плоскости

Рисунок Б.4 — Локальные конфигурации {3,5}, {4,5} и {3,4} на плоскости

Рисунок Б.5 — Локальная конфигурация {5,5,5} на плоскости. Два возможных

случая расположения

Рисунок Б.6 — Локальная конфигурация {5,4,4} на плоскости. Два возможных

случая расположения.

Рисунок Б.7 — Локальная конфигурация {5,5,4} на плоскости. Два возможных

случая расположения

Рисунок Б.8 — Локальная конфигурация {5,5,3} на плоскости

Рисунок Б.9 — Локальная конфигурация {5,5,5,4} на плоскости.

ПРИЛОЖЕНИЕ В Текст программы

В данном приложении приведён полный исходный код программы, реализующей раскраску гексагонального графа с пентагональным вырезом с использованием SAT-подхода. Код включает генерацию графа, формирование CNF, вызов SAT-решателя kissat, интерпретацию результата и визуализацию раскраски.

Перед началом работы производится установка и сборка SAT-решателя kissat, необходимого для проверки выполнимости булевых формул.

Листинг 10: Установка и сборка SAT-решателя kissat

%mkdir temp %cd temp

!git clone https://github.com/arminbiere/kissat.git %cd kissat ! ./conf igure ! make > nul l %cd ../..

!cp temp/kissat/build/kissat kissat

Листинг 11: Инициализация графов, построение шестиугольника и определение

классов эквивалентности

import networkx as nx #import planarity as pl import matplotlib.pyplot as plt import numpy as np a,b = 9,2

edges_dist2 = True edges_dist3 = True dodec = nx.dodecahedral_graph() par = [[],[],[]] 10 npar = 0

n_contr = 0 nei = [] node_list = [] node_cl = [] 15 def valid(x,y,a,b) :

return ((x>=0) and (y>=0) and (x<=a+b) and (y<=a+b) and (x+y>= b) and (x+y<=a+2*b))

25

30

35

40

45

50

def hexagon_triangular_grid(a,b, z edges_dist3 = True): g = nx.Graph () for i in range(a+b+1): for j in range(a+b+1): if valid(i,j,a,b): i1 = (i-2* j ) % 7 j1 = (2*i+3*j) % 7 g.add_node ((i , j , z) if valid(i+1,j-1,a g. add_edge((i,j , z) if valid(i+1,j,a,b) g.add_edge((i,j , z) if valid(i,j+1,a,b) g.add_edge((i,j,z) if edges_dist2: if valid(i+2,j-2,a g.add_edge((i,j,z) if valid(i+2,j-1,a g.add_edge((i,j,z) if valid(i+2,j,a,b) g.add_edge((i,j,z) if valid(i + 1,j +1,a g.add_edge((i,j,z) if valid(i,j+2,a,b) g.add_edge((i,j,z) if valid(i-1,j+2,a g.add_edge((i,j,z) if edges_dist3: if valid(i-3,j+1,a g.add_edge((i,j,z) if valid(i-3,j+2,a g.add_edge((i,j,z) if valid(i-3,j+3,a g.add_edge((i,j,z) if valid(i-2,j+3,a g.add_edge((i,j,z) if valid(i-1,j+3,a g.add_edge((i,j,z) if valid(i,j+3,a,b) g.add_edge((i,j,z) if valid(i+1,j+2,a g.add_edge((i,j,z)

= 0, edges_dist2 = True

col = i 1) b) :

(i+1,j-1,z)) (i + 1, j ,z)) (i,j+1,z)) b) :

(i+2,j-2,z)) b) :

(i + 2,j-1 ,z))

(i + 2, j ,z)) b) :

(i+1,j+1,z))

(i, j+2,z)) b) :

(i-1,j+2,z)) b) :

(i-3, j+1,z)) b) :

(i-3,j+2,z)) b) :

(i-3,j+3,z)) b) :

(i-2,j+3,z)) b) :

(i-1,j+3,z))

(i,j +3 , z) ) b) :

(i+1,j+2,z))

65

70

75

80

85

90

95

if valid(i+2,j+1,a,b): g.add_edge((i,j , z) ,(i + 2,j+1,z)) if val id(i+3,j,a,b) : g.add_edge( ( i , j , z) , (i+3 , j , z) ) return g

def fill_paral(a,b):

global npar

for i in range(b+1):

for j in range(a+1):

par[0].append([j+b-i,i])

for i in range(b+1):

for j in range(a+1):

par [1] .append([i,a+b-j])

for i in range(b+1):

for j in range(a+1):

par [2] .append([a + b-j , b +j-i])

npar = len(par [0])-1

def equiv_nodes(u,v):

e = (u [2] ,v[2])

u 1 = [u [0] ,u[1]]

v1 = [v [0] , v [1]]

if nei [e [0] ]. count (e [1] ) = = 0 :

return False

i0 = nei [e [0] ]. index (e [1] ) i 1 = nei [e [1] ]. index (e [0] ) if par[i0] .count(u1)= = 0 : return False

if par[i1] .count(v1)= = 0 : return False

return (par [i0] .index(u1)+par[i1].index(v1) == npar)

def tr_classes(g):

def merge_classes(c):

for i in range(len(node_list)-1) :

if c.count(node_cl [i]) >0 :

node_cl[i] = c [0]

cln = 0

for u in g.nodes(): cur = []

for k in range(len(node_list)): v = node_list[k] if equiv_nodes(u , v) : if cur.count(node_cl [k])= = 0 : cur.append(node_cl [k])

node_list.append(u) if len(cur)==0: c l n + = 1

node_cl.append(cln) else:

if len(cur)>1 : merge_classes(cur) node_cl.append(cur [0]) def contract_nodes(u,v) :

10 = node_list.index(u)

11 = node_list.index(v) return (node_cl[i0]==node_cl [i1]) def write_dimacs(g,filename):

g1 = nx.convert_node_labels_to_integers(g,first_label=1) f = open(filename ,'w ')

f.write('p edges '+ str(g.number_of_nodes ()) + ' ' + str(g. number_of_edges())+'\\n') for e in g1.edges():

f.write('e '+ str(e [0]) + ' '+ str(e [1]) + '\\n') 120 f. close ()

tr = nx.Graph()

Следующий фрагмент реализует:

— построение преобразованного (усечённого) гексагонального графа с вырезом;

— подготовку к SAT-раскраске: кодирование условий в формате CNF;

— чтение результата из SAT-решателя;

— преобразование координат для круговой визуализации и отображение раскраски графа.

Листинг 12: Формирование выреза, подготовка к SAT-раскраске и визуализация a = 20

colors = [ '#00FFFF' , '#FFFF00 ' , '#FF0000' , '#FF00FF ' , '#00FF00' , '# FF6347' , '#DCDCDC', '#800080' , '#CD5C5C' , '#D2691E' , '#191970 ' , '#008000','#696969' , '#ADD8E6','#008080' , '#8 08000 ' , '#FFFFFF', '#800000 ' , '#FF1493','#000000']

import matplotlib.pyplot as plt from numpy import sin, cos

max a

0.0

def transform(x,y): global max_a 15 a = np.arctan2(y,x) if a < 0.0: a += 2* np.pi

if abs(x) > 0.01 and abs(y) > 0.01 and a > max_a: max_a = a 20 if a > 6.23: print(x, y) a *= 6/5

r = (x*x + y*y)**0.5 return r*cos(a), r*sin(a)

25

def get_pos(i,j) : u = np.array([1.0, 0.0]) v = np.array([0.5, -3**0.5/2]) w = (i-a)*u + (j-a)*v 30 return np . array (transf orm (w [0] , w[1]))

def equiv_nodes(u,v) :

return (u [0] == v [1] ) and (u[1] == v [0] ) and (((u[0]= = a) and ( u [1] >a) and (v[1]= = a)) or ((u[1]==a) and (u[0]>a) and (v [0] = = a)))

35

40

def pent_cap(a,h): g = h.copy () for n in h.nodes(): if n [0] >a and n [1] >a : g.remove_node(n)

return nx.quotient_graph(g, equiv_nodes)

def enc(n, col, ncol): return n*ncol + col + 1

45

def write_cnf_sq(g, dcol, filename, ncol)

nvar = g.number_of_nodes()*ncol

clauses = []