Раскраски случайных подграфов дистанционных графов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Гусев Антон Сергеевич

• Гусев Антон Сергеевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Гусев Антон Сергеевич

1.1 Введение и структура главы

1.2 Число независимости случайного графа $(С(и, 3,1), 1/2)

1.2.1 Формулировки результатов

1.2.2 Доказательство теоремы

1.2.3 Доказательство теоремы

1.2.4 Комментарии

1.3 Хроматическое число случайного графа $(С(и, 3,1), 1/2)

1.3.1 Формулировки результатов

1.3.2 Доказательство теоремы

1.4 Хроматическое число случайного графа $(С(и, 5, 2), 1/2)

1.4.1 Формулировки результатов

1.4.2 Доказательство теоремы

1.5 Число независимости случайного графа $(С(и, 5, 2), 1/2)

2 Хроматическое число случайного подграфа С(и, 2в + 1, в)

2.1 Введение и формулировка результата

2.2 Вспомогательные утверждения

2.2.1 Блоки

2.2.2 Покрытие разбиениями на к-сочетания

2.2.3 Вспомогательная лемма

2.3 Доказательство теоремы

3 Кликовое число случайного подграфа С(п,г,8)

3.1 Кликовое число случайного графа G(С(п,г,8), 1/2) для константных г и

3.1.1 Формулировка результатов

3.1.2 Доказательство теоремы

3.1.3 Доказательство теоремы

3.1.4 Доказательство теоремы

3.2 Кликовое число случайного подграфа Кнезеровского графа С(п,г, 0)

3.2.1 Формулировка результатов

3.2.2 Доказательство теоремы

3.2.3 Доказательство теоремы

3.2.4 Доказательство теоремы

3.2.5 Замечания

Заключение

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

Введение

Базовые определения

Работа посвящена исследованию графов С(п,г, в) = (V(п,г),Е(п,г, в)). Приведем два альтернативных определения для данных графов и сразу покажем, что эти определения являются эквивалентными. Определение 1. Графом

С(п,г,в) = (V (п,г),Е (п,г,в))

со множеством вершин V(п, г) и множеством ребер Е(п, г, в) будем называть граф, у которого

V(п,г) = {х = (х\,Х2, . . . ,Хп) : хг е {0, 1},Х1 + Х2 + ... + Хп = г},

Е(п,г,в) = {{х, у} : (х, у) = в},

где (х, у) — скалярное произведение векторов в евклидовом пространстве. Определение 2. Пусть = {1, 2,... ,п}. Тогда графом

С(п,г,в) = (V (п,г),Е (п,г,в))

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

Покажем, что два данных определения эквивалентны. Действительно, каждой вершине из первого определения можно поставить в соответсвие вершину из вто-

рого определения по следующему правилу: во втором определении будем включать в г-элементное подмножество элемент % из множества тогда и только тогда, когда в первом определении х = 1. Поскольку в первом определении у каждой вершины ровно г координат равны 1, то получившиеся подмножества действительно будут г-элементные. Таким образом каждой вершине из определения 1 поставлена в соответствие вершина из определения 2. Очевидно, что и обратное соответствие будет однозначным.

То, что в первом определении скалярное произведение равно 8, означает, что ровно на 8 координатах в обеих вершинах стоит 1. А тогда у соответствующих вершин из определения 2 будет ровно 8 общих элементов. И вновь очевидно, что в обратную сторону ребрам из определения 2 можно однозначно сопоставить ребра из определения 1. Таким образом, два данных определения эквивалентны.

В дальнейшем будем использовать оба определения, в зависимости от логики рассуждений. Так в некоторых доказательствах будем пользоваться определением 1, а в некоторых — определением

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

Определение 3. Числом независимости а(О) называется число, равное максимальному числу вершин графа О, которые попарно не соединены ребрами.

Определение 4. Кликовым числом ш(О) называется максимальное число, такое что в графе О найдется полный подграф на ш(О) вершинах.

Определение 5. Хроматическим числом х(О) называется число, равное наименьшему количеству цветов, в которые можно так покрасить все вершины графа О, чтобы вершины одного цвета не были соединены ребром.

Подробную информацию о числах независимости, хроматических числах и кликовых числах можно найти в книгах [1], [2] и [3].

Мотивировка из комбинаторной геометрии

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

поскольку ребра у них имеют одну и ту же евклидову длину (см. [4], [5], [6]). В теории кодирования принято название «графы Джонсона» (см. [7]).

Отправной точкой данного исследования служит граф G(n, 3,1), который впервые появился в работе Ж. Надя 1972 года (см. [8]), где он был использован для отыскания конструктивных оценок числа Рамсея (см. [9], [10]). Другое важное применение этот граф нашел в статье Д. Лармана и К. А. Роджерса [11], которая вышла в том же 1972 году и посвящена классическому объекту комбинаторной геометрии — хроматическому числу x(Rn) евклидова пространства Rn:

x(Rn) = min{x : Rn = Vi U ... U Vx, V i V x, y e |x - y| = 1},

где |x — y| — евклидово расстояние. Иначе говоря, хроматическое число пространства — это минимальное количество цветов, в которые можно так покрасить все точки Rn, чтобы между одноцветными точками не было расстояния

Суть наблюдения Лармана и Роджерса состояла в том, что, очевидно, x(Rn) ^ x(G(n, 3,1)), где x(G) — обычное хроматическое число графа G. Таким образом задача отыскания нижней оценки хроматического числа пространства была сведена к оценке хроматического числа конечного графа.

Одна из наиболее стандартных нижних оценок хроматического числа абстрактного графа G = (V, E) имеет вид x(G) ^ OV?).

Ж. Надь доказал следующую теорему.

Теорема 1. Справедлива формула

!n, если n = 0 (mod 4),

n — 1, если n = 1 (mod 4),

n — 2, если n = 2,3 (mod 4).

Из этой теоремы сразу вытекала рекордная на тот момент оценка

,2

x(Rn) ^ x(G(n, 3,1)) ^

O3 n2

а(О(п, 3,1)) 6'

В принципе могло статься, что оценка, найденная с помощью числа независи-

мости, подлежит улучшению. Однако в совместной работе Й. Балога, А. В. Косточки и А. М. Райгородского (см. [12]) была доказана

Теорема 2. Если п = 2к, то х(С(п, 3,1)) = (п-1)6(п-2). В любом случае

-

х(С(п, 3,1)) = п- + О(п).

Таким образом, для графа С(п, 3,1) известно и число независимости, и хроматическое число.

Однако интерес в исследовании графы С(п,г,в) представляют не только в случае г = 3, в = 1, но и в случае произвольных г и в. Во-первых, с помощью этих графов были получены исторически первые экспоненциальные нижние оценки хроматического числа пространства (см. [13]).

Во-вторых, еще одна основополагающая проблема комбинаторной геометрии была предложена Борсуком в 1933 году. Гипотеза состояла в том, что любое множество диаметра 1 в Кп может быть разбито на п +1 часть меньшего диаметра. И эта гипотеза была опровергнута в 1993 году именно с помощью графов С(п,г, в) (см. [6], [14], [15]).

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

В-четвертых, графы С(п, г, в) естественным образом возникают в теории кодирования — при построении равновесных кодов с одним запрещенным расстоянием и при отыскании так называемых матриц Адамара (см. [17], [18]).

Наконец, графы С(п,г,в) служат удобным инструментом для решения некоторых задач в теории однородных гиперграфов (см. [19], [20], [21], [22]).

Отдельно отметим, что в случае, когда в равно нулю, граф С(п,г, 0) принято называть Кнезеровским графом (см. [23]). Этот класс графов представляет самостоятельный интерес и также получил активное исследование в теории графов. Вместе с тем классический полный граф явлется частным случаем Кнезеровского графа при г =

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

графах, их хроматических числах, числах независимости и кликовых числах, а также о их месте и роли в современной комбинаторной геометрии: [24], [25], [26],

[27], [28].

Мотивировка из теории случайных графов

В 1959 году П. Эрдеш и А. Реньи предложили модель случайного графа, которая к настоящему времени очень глубоко изучена (см. [29], [30], [31], [32]). Случайный граф С(п,р) в этой модели — это случайный элемент со значениями во множестве всех графов на п вершинах Уп = {1,... ,п} без петель, кратных ребер и ориентации, имеющий биномиальное распределение, т. е.

Р(С(п,р) = (Vп,Е)) = р|Е|(1 - р)сП-|Е|.

Отметим, что р — вероятность ребра — это, вообще говоря, функция от п.

Одной из важнейших задач о случайных графах Эрдеша-Реньи является задача об отыскании их чисел независимости, хроматических чисел и кликовых чисел. Дабы сформулировать ниже классическую теорему об асимптотическом поведении этих чисел, договоримся о некоторой терминологии. Во-первых, если А — это какое-то свойство графа (например, свойство связности), то будем писать ¥(С(п,р) е А) или, при отсутствии разночтений, просто Р(А), имея в виду вероятность, с которой случайный граф С(п,р) обладает этим свойством. Заметим, что в принципе само свойство может зависеть от п: граф обладает свойством Ап, если его хроматическое число больше П. Во-вторых, будем говорить, что свойство А (или, точнее, последовательность свойств Ап) реализуется с асимптотической вероятностью 1, если ¥(С(п,р) е Ап) ^ 1 при п ^ то. Наконец, пусть / — некоторая функция натурального аргумента п, а д — некоторая функция, определенная на множестве всех графов. Будем говорить, что с асимптотической вероятностью 1 выполнено свойство д(С(п,р)) ~ /(п), если существует еще одна функция ф аргумента п, которая бесконечно мала по отношению к / при п ^ то и с которой

}д(С(п,р)) - /(п)| ^ ф(п)) ^ 1, п ^ то.

Теорема 3. Пусть р — некоторая константа, меньшая 1. Положим ^ = -—р. Тогда с асимптотической вероятностью 1 выполнены соотношения

п

а(О(п,р)) - 2^(прХ ы(О(п,р)) - ^^пр^ х(О(п,Р)) — 210^(пр) •

Для кликового числа и, что двойственно ему, числа независимости, теорема была доказана в работе Б. Боллобаша и П. Эрдеша в 1976 году (см. [33]), для хроматического числа теорему доказал Б. Боллобаш в 1988 году (см. [34]). Многочисленные классические результаты, уточняющие теорему 3, можно найти в работах [31], [32], [35]. Также отметим, что интерес представляет не только асимптотика кликового числа и хроматического числа случайного подграфа полного графа, но и концентрация их значений (см., например, [36], [37]).

Естественное обобщение модели Эрдеша-Реньи устроено следующим образом. Пусть дана некоторая последовательность графов Нп = (УП,Еп), в которой VI ^ го при п ^ го. Заметим, что здесь п не обязательно является числом вершин. Например, можно рассмотреть Нп = О(п, 3,1), в которой |У(п, 3)| = С. Определим случайный граф ^(Нп,р) как случайный элемент со значениями во множестве всех остовных подграфов О = (УП,Е) графа Нп и с биномиальным распределением, т. е.

Р(£ (Нп,р) = (К,£)) = р|Е| (1 - р)|Е«|-|Е|.

Понятно, что О(п,р) = G(Кп,р), где Кп — полный граф на п вершинах.

С одной стороны, очень хорошо изучен случай Нп = где — это п-мерный куб, т. е. граф, вершины которого суть все (0,1)-векторы, а ребра — это пары вершин, различающихся ровно в одной координате (образующих ребро куба). В частности, число независимости случайного подграфа куба исследовалось в работе [38], где доказано, что если р — любая функция от п, с которой рп ^ го при п ^ го, то с асимптотической вероятностью 1 выполнено (^п,р)) — 2п-1. Отметим, что граф подобно графу О(п,г, 8), является дистанционным.

С другой стороны, в последние 20 лет активно развивается наука о свойствах случайных подграфов регулярных графов (см., например, [39]). Глубоко изучены

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

Введение диссертации (часть автореферата) на тему «Раскраски случайных подграфов дистанционных графов»

Цель работы

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

Основные положения, выносимые на защиту

1. Получены верхние и нижние оценки для чисел независимости случайных подграфов графов С(п, 3,1) и С(п, 5, 2), дающие порядок роста соответствующих величин.

2. Получены верхние и нижние оценки для хроматических чисел случайных подграфов графов С(п, 3,1) и С(п, 5, 2), дающие порядок роста соответствующих величин.

3. Улучшена верхняя оценка для хроматического числа случайного подграфа графа С(п, 2в + 1, в).

4. Найдено асимптотическое значение кликового числа случайного подграфа графа С(п,г, в) для случая константных г и в.

5. Найдено асимптотическое значение кликового числа случайного подграфа Кнезеровского графа С(п,г, 0).

Научная новизна

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

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

Степень достоверности и апробация результатов

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

Результаты диссертации опубликованы в 5 работах, представленных в конце списка литературы, — все включены в перечень научных журналов, рекомендованных Московским физико-техническим институтом (МФТИ, Физтех). Все результаты, приведенные в данной диссертации, кроме результатов теоремы 1.2, были получены автором диссертации самостоятельно, включая результаты, опубликованные в совместных работах. Результаты теоремы 1.2 были получены автором совместно с Михаилом Пядеркиным.

Кроме того, по теме диссертации были сделаны доклады на следующих научных конференциях и семинарах:

• «Random Structures and Algorithms 2013», 2013, Познань, Польша.

• «Summit240», 2014, Будапешт, Венгрия.

• «Вероятностные методы в дискретной математике», 2016, Петрозаводск, Россия.

• Научный семинар «Вероятностные методы в комбинаторике» на кафедре математической статистики механико-математического факультета МГУ, под руководством профессора А. М. Райгородского, 2013-2026 гг., неоднократно.

• Семинар кафедры дискретной математики МФТИ, 2013-2026 гг., неоднократно.

Благодарности

Автор благодарит своего научного руководителя Андрея Михайловича Рай-городского за постановку задачи и неоценимую помощь в работе, а также своих соавторов научных публикаций Михаила Пядеркина и Льва Боголюбского за эффективную совместную работу над вопросами, освещаемыми в данной диссертации.

Объем и структура работы

Данная работа состоит из трех глав. Первая глава посвящена изучению числа независимости и хроматического числа для случайных подграфов дистанционных графов С(п, 3,1) и С(п, 5, 2).

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

В рамках третьей главы изучается кликовое число случайных подграфов дистанционных графов С(п,г,в). Во-первых, удалось установить асимптотическое значение кликового числа для семейств случайных подграфов, когда г и в — константы. Во-вторых, удалось определить асимптотическое значение в случае, когда в = 0, а г — функция от п, представимая в виде па+о(1).

Полный объем диссертации составляет 67 страниц. Список литературы содержит 61 наименование.

Глава 1. Число независимости и хроматическое число случайного подграфа С(п, 2в + 1, в)

для в = 1 и в = 2

Первая глава данной работы посвящена изучению чисел независимости и хроматических чисел случайных подграфов графов С(п, 3,1) и С(п, 5, 2). Результаты этой главы опубликованы в работах [57] и [58].

1.1. Введение и структура главы

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

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

Прежде всего очевидно, что если в (0,1)-векторах зафиксировать одно и то же множество из в + 1 единиц, то они не будут иметь скалярное произведение, равное в. Это значит, что

а(С(п,г,в)) ^ сг=;=! = 0 (п—1).

С другой стороны, можно, наоборот, наложить ограничение, что попарные скалярные произведения не превосходят в — 1, как это обычно делают в теории кодов, исправляющих ошибки (см. [17]). При таком подходе работает теорема Рёдля (см.

[40] и [41]), из которой следует, что

Св

а(С(п,г,в)) > (1 + о(1))^ = в(пв).

Сг

Понятно, что при г = 2в + 1 оценки имеют одинаковый порядок, при г > 2в + 1 сильнее первая оценка, а при г < 2в + 1 сильнее вторая оценка.

Верхние оценки получаются с помощью линейно-алгебраического метода (см. [25]), и для них существенно, чтобы разность г — в была степенью простого числа. Например, графы С(п, 3,1) и С(п, 5, 2) удовлетворяют этому условию. Если оно выполнено, то теорема Франкла-Уилсона (см. [13]) говорит, что

а(С(п,г,в)) < (1 + о(1))Сг-'-1 = в (пг—^ , г ^ 2в + 1,

С 2в—г+1с г—в —1

а(С(п, г, в)) ^ (1 + о(1)) п с2а—г+1 = в (пв), г < 2в + 1,

где символ в означает, что равенство выполнено с точностью до положительных констант в верхней и нижней оценке.

Таким образом, при всех г и в, разность которых — степень простого, известен порядок роста числа независимости, а при г ^ 2в + 1 и том же ограничении на разность известна даже его асимптотика. Еще раз подчеркнем, что это специфика постоянных г и в. При этом без условия на разность г — в оценки, как правило, существенно слабее.

Видим, что именно в случае г = 2в+1 для графов С(п, г, в) различные подходы к оценке числа незавимомсти дают совпадающие по скорости роста результаты. Аналогичная ситуация наблюдается и для оценки хроматического числа.

Нижние оценки являются следствием верхних оценок числа независимости. Иными словами, при г — в = а1, а — простое число, выполнены неравенства

С г

Х(0(п,г,в)) > п =П (пв+1) , г ^ 2в + 1,

а(и(п,г, в)) 4 у

гчт

где запись ^ (д(п)) = /(п) означает, что существует такая константа с > 0 и п0,

Х(0(п,г,в)) > п =П (пг—, г < 2в + 1,

а(и(п,г, в)) 4 у

что /(п) ^ с • д(п) ^ 0 при всех п ^ по.

Для получения верхних оценок известны два подхода. Во-первых, есть теорема Брукса.

Теорема Брукса, [42]. Пусть Д(О) — максимальная степень вершины графа О. Если граф О связен и не является ни полным графом, ни простым (несамо-пересекающимся) циклом нечетной длины, то х(О) ^ Д(О).

При этом исследуемые дистанционные графы регулярны, т.е. все степени вершин в них одинаковы и равны ССП—Г, а также связны и отличны от простого цикла нечетной длины. Тогда, применив теорему Брукса, легко получаем, что

х(о(п,г,в)) ^ ? = о (п-').

Во-вторых, существует способ покрыть множество V(п,г) независимыми множествами — цветами, — каждый из которых состоит из всех вершин, содержащих данное (в + 1)-элементное подмножество множества Тогда, конечно, х(О(п, г, в)) < СП+1 = О (п5+1).

В итоге, учитывая все полученные нижние и верхние оценки, получим порядок роста хроматического числа О(п, г, в) во всех случаях, когда разность г — в — это степень простого.

Отметим, что вновь различные подходы дают одинаковую скорость роста именно для случая, когда г = 2в + 1.

В рамках данной главы будут изучены число незавимимости и хроматическое число для случайных подграфов графов О(п, 3,1) и О(п, 5, 2), получив соответствующие верхние и нижние оценки. В параграфах 1.2 и 1.3 подробно остановимся на числе независимости и хроматическом числе соответсвенно для случайного подграфа графа О(п, 3,1). В параграфе 1.4 получим оценки хроматического числа для случайного подграфа графа О(п, 5, 2), а в параграфе 1.5 обсудим число назавимисимости этого графа.

1.2. Число независимости случайного графа ^(0(п, 3,1), 1/2)

1.2.1. Формулировки результатов

Ранее уже использовалась терминология «асимптотическое равенство выполнено с асимптотической вероятностью 1». В аналогичном смысле будем понимать и асимптотические неравенства, т.е. утверждение «выполнено д(д(С(п, 3,1), 1/2)) ^ (1 + о(1))/(п) с асимптотической вероятностью 1» (здесь всякий раз будет /(п) ^ то при п ^ то) означает существование такой функции ф аргумента п, что ф = о(1) при п ^ то и

Р(д(£(С(п, 3,1), 1/2)) < (1 + ф(п))!(п)) ^ 1, п ^ то.

Теорема 1.1. С асимптотической вероятностью 1 справедливо неравенство

а(д(С(п, 3,1), 1/2)) < 4(1 + о(1))пlog2 п.

Теорема 1.2. С асимптотической вероятностью 1 справедливо неравенство

а(д(С(п, 3,1), 1/2)) ^ 2(1 + о(1))пlog2 п.

Таким образом, получены практически неулучшаемые оценки: константы в них отличаются лишь в два раза. Отметим, что оценки из теорем 1.1 и 1.2 можно записать в виде

а(д(в(п, 3,1), 1/2)) = в (а(С(п, 3,1)) V(п, 3)|)).

Этот результат хорошо согласуется с классической теоремой 3, поскольку там а(Кп) = 1, а ^(|К|) = log2п.

1.2.2. Доказательство теоремы 1.1

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

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

ЕХк =

Р(А является независимым множеством в G(О(п,3,1), 1/2)) =

Асу (п,з), |А|=к

= ^ 2 — |{{х,у}€Е(п,3,1): х,уеА}|, Асу (п,з), |А|=к

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

Теорема Турана, [43]. Пусть дан граф О = (V, Е). Тогда число ребер в таком графе не меньше, чем

IV |

IV!

а(О)

— а(О)

Г IV| 1 ( Г IV| 1

а(С) 1 а(С)

+ 1

2

Получаем, что если к > а(О(п,3,1)), то можно не только гарантировать наличие ребер в таком подграфе, но и эффективно оценить снизу число этих ребер. Дабы записать оценку, напомним, что а(О(п, 3,1)) ~ п, а значит, к ^ го при п ^ го. Тогда, применив теорему Турана для рассматриваемого подграфа на множестве вершин А, учитывая, что число независимости подграфа не превосходит числа незавимисоти исходного графа, получаем следующую оценку для числа ребер

|{{х,у} е Е(п,3,1) : х,у е А}| ^ (1 + о(1))

к2 к2 2а(О(п, 3,1)) = (1 + °(1))2п'

Имея такую оценку, получаем, что

_ 2 2

EXk ^ ^ 2-(1+0(1))2n = Ckcs2-(1+о(1))i.

AcV(n,3), |A|=k

Хорошо известно, что Cba ^ (iff, где e — основание натурального логарифма. Следовательно,

/ n3 \k 2 2

EXk ^ (у j 2-(1+o(1))kn = 23k log2 n-clog2 k-(1+o(1))kn.

Видно, что существует функция k = k(n), которая асимптотически ведет себя как 4nlog2 n и с которой EXk ^ 0 при n ^ то. Отсюда с учетом неравенства Маркова вытекает утверждение теоремы:

P(a(G (G(n, 3,1), 1/2)) < 4(1 + o(1))n log2 n) = P(Xk = 0) ^ 1 - EXk ^ 1, n ^ то. Теорема доказана.

1.2.3. Доказательство теоремы 1.2

Если рассуждение из предыдущего параграфа было вполне стандартным и никак не использовало специфику графа G(n, 3,1) (за исключением величины его числа независимости), то здесь потребуется в большей мере опираться на структуру графа. Прежде всего введем ряд обозначений и терминов.

Пусть Rn = {1,..., n}. Каждой вершине x £ V(n, 3) можно поставить в естественное соответствие тройку элементов из Rn: это будут номера координат, на которых у вектора x находятся единицы. Тогда ребро в графе G(n, 3) — это пара троек, пересекающихся ровно по одному элементу.

Кликой в графе называется любой полный подграф, т.е. подграф, в котором проведены все возможные ребра. Размер максимальной клики, как уже было сказано во введении, в абстрактном графе G называется кликовым числом и обозначается w(G). Это обозначение хорошо согласуется с обозначением числа независимости a(G), которое в понятном смысле двойственно ему.

Для графа О(п, 3,1) любая клика — это набор троек в попарные пересечения которых имеют мощность 1. Ясно, что ¡х>(О(п, 3,1)) ~ | при п ^ го (фиксируется один элемент а оставшаяся часть множества разбивается на непересекающиеся пары).

Дальнейшая идея состоит в том, что, оказывается, в графе О(п, 3,1) можно выбрать «почти» п «почти» максимальных клик, между которыми, однако, нет ни одного ребра.

Итак, положим т = 2

, где [х] — это обычная целая часть чис-

2 п

ла х. Разобьем на части Л1 = и Я2 = \ Л1. Сперва опишем

построение одной клики Для этого возьмем в Л1 непересекающиеся пары {1, 2}, {3,4}, {5,6},..., {т — 1,т} (т четное). К каждой из этих пар добавим элемент т + 1 е Я2. Это и есть искомая клика. Число вершин в ней т ~ 2к>п п, п ^ го, т.е. оно отличается от максимально возможного лишь в примерно логарифм раз. Аналогично построим еще п — т — 1 клику ф2,..., фп—т, добавляя к каждой из выбранных ранее пар в Л1 элемент т + 2 е Я2, элемент т + 3 е Я2 и так далее. Очевидно, что для любых г, ^, г = ^, и для любых х из у из фу ребра между х, у нет: эти тройки могут либо вовсе не пересекаться, либо пересекаться сразу по какой-то паре из Л1.

Случайный граф ^(О(п, 3,1), 1/2) получается из графа О(п, 3,1) в результате взаимно независимого выбора ребер из Е(п, 3,1) с одной и той же вероятностью 2, поэтому на кликах ф1,... , фп—т возникают независимые копии случайного графа Эрдеша-Реньи О(т/2,1/2). Отметим, что эти копии независимы и с точки зрения теории вероятностей (как случайные элементы), и с точки зрения теории графов (между ними нет ребер).

При р = 2 теорема 3 говорит, что с асимптотической вероятностью 1 выполнено а(О(т/2,1/2)) ~ 21с^2т при т ^ го, но т лишь в логарифм раз меньше п, откуда а(О(т/2,1/2)) ~ 21с^2п при п ^ го. Более того, скорость стремления вероятности к единице очень высока (см. [30], [31], [40]). Заведомо при правильно подобранной бесконечно малой и больших п верна оценка

а(О(т/2,1/2)) ^ 2(1 + о(1))^2 п) ^ 1 — е—п.

п

А это значит, что

Р(У г = 1,...,п — т а(д ((г, 1/2)) ^ 2(1 + о(1))^2 п) ^

^ (1 — е п) — 1, п — то.

Следовательно, с асимптотической вероятностью 1 в случайном графе д(С(п, 3,1), 1/2) есть п — т независимых множеств размера 2(1 + о(1))^2 п, между которыми точно нет ребер. Вместе они составляют, тем самым, одно независимое множество размера 2(п —т)(1 + о(1))^2п ~ 2пп, что и требовалось доказать.

1.2.4. Комментарии

Утверждение и доказательство теоремы 1.1 можно вложить в существенно более общий контекст. Справедлива

Теорема 1.3. Пусть дана некоторая последовательность графов Нп = (Уп,Еп), в которой |Уп| — то при п — то. Рассмотрим случайный граф д(Нп,р) с произвольной вероятностью ребра р = р(п). Пусть к = к(п) — произвольная функция, с которой выполнено

^ (1 — р)1«х>у№:х,у£А}\ — 0, п —У то.

АсУи, \А\=к

Тогда с асимптотической вероятностью 1 имеет место неравенство

а(д(Нп,р)) < к.

Доказательство теоремы 1.3 не приводим ввиду его очевидности. В подпараграфе 1.2.2 была использована оценка Турана для величины |{{х, у} £ Е(п, 3,1) : х, у £ А}|. Конечно, могло оказаться, что эта оценка не точна. Однако оценка достигается, причем именно на конструкции из клик, которая использована для доказательства в подпараграфе 1.2.3. Действительно, пусть ..., Qn—m — те самые клики. Пусть к = к(п) — произвольная функция, асимптотически ведущая себя как 4п log2 п. Оценка Турана имела в этом случае вид

|{{х,у} е Е(п,3,1) : х,у е А}| ^ 8(1 + о(1))п 1о§2п.

Рассмотрим любое множество А мощности к, у которого мощности пересечения с множествами вершин рассматриваемых клик примерно одинаковы. Тогда эти мощности асимптотически равны 4^2 п. Значит, число ребер в подграфе графа О(п, 3,1), порожденном таким множеством А, асимптотически равно 8п^2 п. Ясно, что описанных множеств А очень много, и, если стремиться к улучшению именно верхней оценки числа независимости, то нужно аккуратно классифицировать различные А с V(п, 3) по количеству ребер графа О(п, 3,1), которые в них проведены. Даже для графа О(п,3,1) — это трудная задача (см. [44], [45], [46],

[47]).

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

1.3. Хроматическое число случайного графа 0(О(п,3,1), 1/2

1.3.1. Формулировки результатов

Следующая теорема является тривиальным следствием теоремы 1.1 и оценки Х(О) ^ От?). Приводим ее без доказательства ввиду его очевидности.

Теорема 1.4. С асимптотической вероятностью 1 справедливо неравенство

1 п2

Х(0(О(п,3,1), 1/2)) ^ -(1+ о(1)) п

24 п

Гораздо более сложным для доказательства является тот факт, что оценку из теоремы 1.4 принципиально улучшить нельзя.

Теорема 1.5. С асимптотической вероятностью 1 справедливо неравенство

1 п2

Х(0(О(п, 3,1), 1/2)) ^ -(1 + о(1))- п

6 1о§2п

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

1.3.2. Доказательство теоремы 1.5

Введем вспомогательную конструкцию: разобьем множество вершин графа С(п, 3,1) — множество «троек» — на своего рода слои. После этого будем вести раскраску вершин случайного графа отдельно по слоям.

Итак, начнем с построения первого слоя, который обозначим 51. Для этого разделим п на 4 с остатком: п = 4й1 + ¿1, ^ 3. Положим = , Л1 = {2й1 + 1,..., 4й1}, Т1 = {4й1 + 1,..., п}, так что Яп = и Л1 и Т1. Назовем левой половинкой, Л1 правой половинкой, а Т довеском.

Совершенным паросочетанием в любой из половинок называется разбиение этой половинки на двухэлементные множества — пары. Например, совокупность пар {1, 2}, {3,4},..., {2й1 — 1, 2й1} образует совершенное паросочетание в левой половинке. Хорошо известно (см. [1]), что множество всех пар в разбивается на непересекающиеся совершенные паросочетания. Поскольку всего пар , а в каждом паросочетании их й1, выходит, что общее число паросочетаний в разбиении равно 2й1 — 1. Обозначим эти паросочетания М1,..., М2в1_ 1. Аналогичные паросочетания в Л1 обозначим N1,..., Ж2в1—1.

Зафиксируем паросочетание М^. К каждой паре в нем добавим элемент ] е Л1. Образуется клика из троек в графе С(п, 3,1). Совокупность всех 2й1 таких клик — это блок (см. §§1.1.4). В общей сложности имеем 2й1 — 1 блоков по 2й1 клик в каждом. Аналогично строим 2й1 — 1 блоков по паросочетаниям из правой половинки. Обозначим полученные блоки А1,..., А2в1—1 и В1,..., В2в1—1 соответственно.

Множество троек, которые имеют общие элементы с довеском Т1, обозначим С1. В итоге в слой определим все тройки из блоков А1,..., А2в1—1 и

В, . . . , £2*1 — 1.

Ни в первый слой, ни в С1 не попали только те тройки, которые либо целиком лежат в Ь1, либо целиком лежат в Л1. Как в графе С(п, 3,1), так, тем более, и в его случайном подграфе тройки из разных половинок попарно несмежны. Поэтому про правую половинку можно забыть и красить лишь содержимое левой (см., впрочем, замечание 1.1 в конце доказательства). С левой же половинкой поступаем

ровно так же, как, строя слой £1, поступили со всем Иными словами, полагаем 251 = 4й2 + ¿2, ¿2 < 3, ¿2 = П2з2, Я2 = {2в2 + 1, . . . , 4в2}, Т2 = {4в2 + 1, . . . , 2в1}, так что Ь1 = Ь2 и Я2 и Т2. Строим 4в2 — 2 блоков и множество троек С2, имеющих непустые пересечения с Т2. В слой £ кладем все тройки из блоков.

И так далее. На выходе имеем последовательность слоев £ и дополнительных множеств С к. В слое £ находится 4вк — 2 блоков, в каждом таком блоке 2вк клик, и у каждой из этих клик вк вершин. При этом слой £ локализован в множестве

I1,..., 2^1.

Теперь перейдем к случайному графу д(С(п, 3,1), 1/2) и его раскраске. Прежде всего раскрасим его вершины, расположенные в множествах С к. Здесь случайность роли не играет, осуществим покраску с запасом, т.е. сделаем ее в исходном графе С(п, 3,1). Очевидно, что в этом случае на вершины из Ск уйдет не больше 3(4вк + 3) цветов. В сумме имеем

£ 3(4вк + 3) < 3 ((п + 3) + (п + 3) + (п + 3) + ..) = е(п).

к

2

Как видно из утверждения теоремы, в котором цветов порядка ^ п, это количество не внесет значительного вклада в итоговый результат.

Рассмотрим слои. Сперва выберем из них те, чьи номера больше величины log2 п + 1. Все эти слои локализованы в множестве |1,..., п |. Снова забудем про случайность и воспользуемся с запасом раскраской графа

а

, 3,11 .В работе [12] показано, что на эту раскраску уйдет порядка

^2 п

1о^2 п

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

Остаются слои с номерами к ^ log2 log2 п + 1. Заметим, что в этих слоях вк — то при п — то и, более того, вк ~ log2 п. Пусть дан какой-то из этих слоев. Рассмотрим один из блоков в нем. Каждая клика в этом блоке имеет вк вершин, и в случайном графе д(а(п, 3,1), 1/2) на ней образуется случайный граф Эрдеша-Реньи а(вк, 1/2). По теореме 3 этот граф с высокой вероятностью красится в (1 + о(1))21о^ ^ цветов. При правильно подобранной бесконечно малой и больших п «высокая вероятность» — это 1 — е—^ ^ 1 — е—п/ 1о®2 п (см. [30], [31], [40]). Последняя величина, даже возведенная в степень, равную числу всех клик во всех

блоках всех рассматриваемых слоев, стремится к единице. Поэтому с асимптотической вероятностью 1 каждый блок можно покрасить в (1 + о(1))21о*к ^ цветов. Следовательно, на слой уйдет

(1 + о(1))-^- = (1 + о(1))г^- = (1 + о(1)) п2

2 1о§2 йк 1о^2 22к+1 1о§2 п

красок. Суммарно имеем

1о^2 ^ п+1 2

£ (1 + < + ^''г—Т! ■ = 1(1 + 0(1))1оп2п-

к— 1

и теорема доказана.

Замечание 1.1. В процессе доказательства не учитывались некоторые половинки. Естественно, предполагалось, что на их покраску уйдет столько же цветов, сколько ушло на покраску половинок, задействованных в слоях (тех же самых цветов). На самом деле в итоговой оценке вероятности следовало учитывать все клики из таким образом «потерянных» блоков. Однако и их не так много, чтобы величина 1 — е—п/ 1о®2 п за счет возведения в соответствующую степень перестала стремиться к единице.

1.4. Хроматическое число случайного графа 0(^(п, 5, 2), 1/2)

1.4.1. Формулировки результатов

Логичным продолжением исследования графа С(п, 3,1) является граф С(п, 5,2), который впервые был изучен в 1978 году в работе Д. Лармана (см. [48]).Продолжая те подходы, что были применены в предыдущем параграфе, можно получить верхнюю оценку хроматического числа случайного графа 0(С(п, 5, 2), 1/2).

Теорема 1.6. С асимптотической вероятностью 1 справедливо неравенство

8 п3

Х(0(С(п, 5, 2), 1/2)) ^ 8 п

147 п

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

1.4.2. Доказательство теоремы 1.6

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

Вершины графа а(п, 5,2) суть пятиэлементные подмножества множества

= {1,..., п} — «пятерки». Разобьем их на слои, как это было сделано в подпараграфе 1.3.2. Опишем построение первого слоя £1. Для этого разделим п на 24 с остатком: п = 24в1 + ¿1, ^ 23. В чем смысл такого, на первый взгляд, странного деления, станет ясно чуть позже.

Положим Ь1 = Я12в1, Я1 = {12в1 + 1,..., 24в1}, Т1 = {24в1 + 1,... ,п}. Как и в подпараграфе 1.3.2, это левая половинка, правая половинка и довесок. Сохраняя обозначения подпараграфа 1.3.2, назовем С1 множество пятерок, имеющих непустые пересечения с довеском Т1. В слой же £ отправим все пятерки, которые не лежат целиком ни в одной из половинок (см. §§1.3.2). Будем разбивать слой на блоки из клик, между которыми нет ребер. Здесь есть два существенно разных случая: пятерка из £ разбивается половинками Ь1,Я1 на «тройку» и «двушку»; пятерка из £ разбивается половинками Ь1,Я1 на «четверку» и «однушку». Можно считать, что в первом случае тройка находится в ¿1, а во втором случае в Ь1 расположена четверка. Если найдем количество покрывающих блоков в таком предположении, то итоговое число блоков будет просто вдвое большим. Первый случай проще.

Случай 1. Назвоем совершенным тройкосочетанием в левой половинке любое ее разбиение на непересекающиеся тройки. Такие разбиения существуют, поскольку величина \Ь11 = 12в1 делится на 3 (это одна из причин выбора параметра 24). Обратимся к классической теореме Бараньяи.

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

Теорема Бараньяи, [49]. Все к-элементные подмножества пк-элементного множества можно покрыть непересекающимися совершенными разбиениями на к-сочетания.

Применив данную теорему для к = 3, получаем, что множество всех троек в

Ь1 разбивается на непересекающиеся совершенные тройкосочетания. Общее число

с3

этих тройкосочетаний равно — 72в1 (асимптотика понимается при п — то). Один блок — это фиксированное тройкосочетание, к каждой тройке которого сперва добавлена одна двушка из Я1 (образуется одна клика в графе а(п, 5, 2)), потом добавлена вторая двушка из Я1 (образуется еще одна клика в графе а(п, 5, 2)), и так далее, пока не закончатся двушки, а вместе с ними и клики блока. Итого имеем (1 + о(1))72в2 блоков, состоящих из С2251 клик размера 4в1. Между кликами внутри блока нет ребер, т.к. пятерки из разных клик имеют либо меньше двух элементов в пересечении (если отвечающие им тройки в Ь1 не пересекаются), либо не меньше трех общих элементов (если отвечающие им тройки совпадают). Очевидно также, что блоками исчерпаны все пятерки в рамках случая.

Если сразу перейти к случайному графу, то с высокой вероятностью число цветов в оптимальной раскраске каждого блока не превзойдет величины ),

откуда следует, что общее число цветов не больше

Список литературы диссертационного исследования кандидат наук Гусев Антон Сергеевич, 2026 год

Литература

[1] Харари, Ф. Теория графов. — Мир, Москва, 1973.

[2] Оре, О. Теория графов. — Наука, Москва, 1980.

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

[4] Brass P., Moser W. O., Pach J. Research problems in discrete geometry. — Springer, 2005. — Vol. 18.

[5] Raigorodskii A. M. Coloring Distance Graphs and Graphs of Diameters // Thirty essays on geometric graph theory. — 2013. — Pp. 429-460.

[6] Raigorodskii A. M. Cliques and cycles in distance graphs and graphs of diameters. // Discrete geometry and algebraic combinatorics. — 2014. — Pp. 93109.

[7] Raigorodskii A. M. Combinatorial geometry and coding theory // Fundamenta Informaticae. — 2016. — Vol. 145, no. 3. — Pp. 359-369.

[8] Nagy Z. A certain constructive estimate of the Ramsey number // Matematikai Lapok. — 1972. — Vol. 23. — Pp. 301-302.

[9] Graham R. L., Rothschild B. L., Spencer J. H. Ramsey theory. — John Wily and Sons, NY, Second Edition, 1990.

[10] Райгородский, А. М. Вероятность и алгебра в комбинаторике. — МЦНМО, Москва, 2010.

[11] Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean space // Mathematika. — 1972. — Vol. 19, no. 1. — Pp. 1-24.

13

14

15

16

17

18

19

20

21

22

Balogh J., Kostochka A. V., Raigorodskii A. M. Coloring some finite sets in Rn // Discussiones Mathematicae Graph Theory. — 2013. — Vol. 33, no. 1. — Pp. 25-31.

Frankl P., Wilson R. Intersection theorems with geometric consequences // Combinatorica. — 1981. — Vol. 1. — Pp. 357-368.

Райгородский, А. М. Вокруг гипотезы Борсука // Итоги науки и техники. Серия «Современная математика». — 2007. — Т. 23. — С. 147-164.

Boltyanski V. G., Martini H., Soltann P. S. Excursions into combinatorial geometry. — Universitext, Springer-Verlag, Berlin, 1997.

Raigorodskii A. M. Three lectures on the Borsuk partition problem // London Mathematical Society Lecture Note Series. — 2007. — Vol. 347. — Pp. 202-248.

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

Hedayat A., Wallis W. D. Hadamard matrices and their applications // Annals of Statistics. — 1978. — Vol. 6, no. 6. — Pp. 1184-1238.

Райгородский, А. М, Шабанов, Д. А. Задача Эрдеша-Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы // Успехи математических наук. — 2011. — Т. 66, № 5. — С. 109-182.

Frankl P., Kupavskii A. Partition-free families of sets // Discrete Mathematics. — 2018. — Vol. 341, no. 7. — Pp. 2080-2082.

Frankl P., Kupavskii A. Families of sets with no matching of sizes 3 and 4 // European Journal of Combinatorics. — 2019. — Vol. 75. — Pp. 123-135.

Balogh J., Cherkashin D., Kiselev S. Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs // European Journal of Combinatorics. — 2019. — Vol. 79. — Pp. 228-236.

Бобу, А.В., Куприянов, А.Э., Райгородский А.М. О хроматических числах дистанционных графов, близких к Кнезеровским // Доклады РАН. — 2016. — Т. 468, № 3. — С. 247-250.

[24] Райгородский, А. М. Проблема Борсука и хроматические числа некоторых метрических пространств // Успехи математических наук. — 2001. — Т. 56, № 1. — С. 107-146.

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

[26] Agarwal P. K, Pach J. Combinatorial geometry. — John Wiley and Sons Inc., New York, 1995.

[27] Soifer A. The Mathematical Coloring Book. — Springer, 2009.

[28] Klee V. K., Wagon S. Old and new unsolved problems in plane geometry and number theory. — Math. Assoc. America, Washington, DC, 1991.

[29] Erdos P., Renyi A. On random graphs I // Publ. Math. Debrecen. — 1959. — Vol. 6. — Pp. 290-297.

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

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

[32] Janson S., L uczak T, Rucinski A. Random Graphs. — Wiley, NY, 2000.

[33] Bollobas B., Erdos P. Cliques in random graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1976. — Vol. 80, no. 3. — Pp. 419-427.

[34] Bollobas B. The chromatic number of random graphs // Combinatorica. — 1988.

— Vol. 8. — Pp. 49-55.

[35] L uczak T. The chromatic number of random graphs // Combinatorica. — 1991.

— Vol. 11, no. 3. — Pp. 45-54.

[36] L uczak T. A note on the sharp concentration of the chromatic number of random graphs // Combinatorica. — 1991. — Vol. 11, no. 3. — Pp. 295-297.

[37] Heckel A. Non-concentration of the chromatic number of a random graph // Journal of the American Mathematical Society. — 2021. — Vol. 34. — Pp. 245-260.

[38] Weber K. F. E. On the independence number of random subgraphs of the n-cube // Annals of Discrete Math. — 1987. — Vol. 33. — Pp. 333-337.

[39] Krivelevich M., Sudakov B. Pseudo-random graphs // Bolyai Society Mathematical Studies. — 2006. — Vol. 15. — Pp. 199-262.

[40] Алон, Н., Спенсер, Д. Вероятностный метод. — Бином. Лаборатория знаний, Москва, 2007.

[41] Rodl V. On a packing and covering problem // European J. Combin. — 1985. — Vol. 6. — Pp. 69-78.

[42] Brooks R. L. On colouring the nodes of a network // Proc. Cambridge Philosophical Society, Math. Phys. Sci.. — 1941. — Vol. 37. — Pp. 194-197.

[43] Turan P. Egy grafelmeleti szelsoertekfeladatrol // Mat. es Fiz. Lapok. — 1941. — Vol. 48. — Pp. 436-453.

[44] Пушняков Ф.А. О числе ребер в индуцированных подграфах специального дистанционного графа // Математические заметки. — 2016. — Т. 99, № 4.

— С. 550-558.

[45] Пушняков Ф.А. Новая оценка числа ребер в индуцированных подграфах специального дистанционного графа // Проблемы передачи информации. — 2015.

— Т. 51, № 4. — С. 371-377.

[46] Пушняков Ф.А. О количествах ребер в порожденных подграфах некоторых дистанционных графов // Математические заметки. — 2019. — Т. 105, № 4.

— С. 592-602.

[47] Пушняков Ф.А.. Райгородский А.М. О количествах ребер в порожденных подграфах некоторых дистанционных графов // Математические заметки. — 2020. — Т. 107, № 2. — С. 286-298.

[48] Larman D. G. A note on the realization of distances within sets in Euclidean space.

— 1978. — Vol. 53, no. 4. — Pp. 529-535.

[49] Baranyai Z. On the factorization of the complete uniform hypergraph // Colloquia Math. Soc. Janos Bolyai. — 1973. — Vol. 10. — Pp. 91-107.

[50] Тараканов Комбинаторные задачи и (0,1)-матрицы. — Наука, Москва, 1985.

[51] Sidorenko A. F. What we know and what we do not know about Turan numbers // Graphs and Combinatorics. — 1995. — Vol. 11. — Pp. 179-199.

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

[53] Пядеркин, М.М. Числа независимости случайных подграфов некоторого дистанционного графа // Математические заметки. — 2016. — Vol. 99, no. 2. — Pp. 288-297.

[54] Пядеркин, М.М. О хроматическом числе случайного подграфа некоторого дистанционного графа // Труды МФТИ. — 2018. — Vol. 10, no. 4. — Pp. 5-13.

[55] Пядеркин, М.М. Числа независимости случайных подграфов дистанционных графов // Математические заметки. — 2016. — Т. 99, № 4. — С. 564-573.

[56] Pyaderkin M. On the stability of some Erdos-Ko-Rado type results, // Discrete Mathematics. — 2017. — Т. 340, № 4. — С. 822-831.

Публикации автора по теме диссертации

[57] Боголюбский Л.И., Гусев А.С., Пядеркин М.М., Райгородский А.М. Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов // Доклады РАН. — 2014. — Т. 457, № 4. — С. 383-387.

[58] Боголюбский Л.И., Гусев А.С., Пядеркин М.М., Райгородский А.М. Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов // Математический сборник. — 2015. — Т. 206, № 10.

— С. 3-36.

[59] Гусев А.С. Новая верхняя оценка хроматического числа случайного подграфа дистанционного графа // Математические заметки. — 2015. — Т. 87, № 3.

— С. 342-349.

[60] Гусев А.С. Кликовые числа случайных подграфов некоторых дистанционных графов // Проблемы передачи информации. — 2018. — Т. 54, № 1. — С. 73-85.

[61] Гусев А.С. О кликовом числе случайного подграфа одного кнезеровского графа // Труды МФТИ. — 2026. — Т. 18, № 1. — С. 99-106.