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

• Кошелев Михаил Михайлович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Кошелев Михаил Михайлович

Введение

Глава 1. Клико-хроматические числа графов Джонсона

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

1.2 Новые результаты

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

1.3.1 Доказательство нижних оценок

1.3.2 Случай г = 3,8 =

1.3.3 Верхние оценки клико-хроматических чисел

Глава 2. Модулярность и другие характеристики графов

Джонсона

2.1 Введение и предыдущие результаты

2.2 Основные результаты

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

2.4 Доказательство вспомогательных утверждений

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

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

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

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

2.4.5 Доказательство лемм

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

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

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

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

2.5 Доказательство основных результатов

2.6 Другие применения спектральных методов

2.6.1 Гигантская компонента в графах Джонсона

2.6.2 Гамильтоновость случайных подграфов с(4й, 28,8)

2.6.3 Вершинная связность (п,(1, Л)-графов

Глава 3. Модулярность в модели посаженного разбиения

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

Стр.

3.2 Регулярные взвешенные графы

3.2.1 Определения

3.2.2 Свойства (п,й, Л)-взвешенных графов

3.3 Связь (п,(1, Л)-взвешенных графов и случайных графов

3.3.1 Основной результат

3.3.2 Вспомогательные леммы

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

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

Заключение

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

Введение

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

Графы Джонсона

Дадим определение семейства графов G(n,r,s), известных также как графы Джонсона. Именно этому семейству графов будет посвящена большая часть данной работы.

Определение 1. Пусть п > г > s ^ 0 — целые числа. Определим граф Джонсона G(n,r,s) как граф, у которого множество вершин совпадает с множеством n-мерных векторов с координатами из {0,1} и нормой у/г, а ребро проводится между парами вершин, у которых скалярное произведение соответствующих им векторов в точности равно s. Более формально,

G(n,r,s) = (К,г,ЕЩГ^),УЩГ = {v е {0,1}п : |Н|2 = г},

En,r,s = {(u,v) е Vn,r х Vn,r : (u,v) = s}.

Заметим, что граф G(n, г, s) изоморфен графу отношения "лежать на расстоянии у72(r — s)" для множества вершин n-мерного единичного куба с евклидовой нормой, равной у/г. Именно этот факт является ключевым для многих применений графов Джонсона в комбинаторной геометрии (см. [1—7]) и объясняет другое частое название таких графов — дистанционные графы. Помимо комбинаторной геометрии, данные графы нашли широкое приложение в задачах теории кодирования (см. [8, 9]) , теории гиперграфов (см. [10]) , а также теории Рамсея (см. [11]). В последние годы появилось множество исследований различных свойств графов Джонсона (см [12—18]).

В некоторых случаях нам будет удобнее пользоваться другим определением графа G(n,r,s). Сформулируем его.

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

Графы Ср(п, г, в)

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

Определение 3. Пусть п > г > в ^ 0 — целые числа, а р Е [0,1]. Тогда Ср(п,г,з) — случайный элемент на множестве всех графов, задавемый соотношениями Р(Ср(п,г, в) = С) = р\Е°\(1 — р)\Еа(п,т,в)\—\Е0\, если С является остовным подграфом С(п,г,з) и Р(Ср(п,г, з) = С) = 0 в противном случае. В вышеуказанных формулах Ее и — множества ребер графов С и

С(п, г, в) соответственно.

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

Модель посаженного разбиения

Одна из глав диссертации посвящена изучению еще одной модели случайного графа, а именно модели посаженного разбиения. Дадим определение данной модели.

Определение 4. Зафиксируем натуральные числа к,пх,...,пк и действительные числа р,д € [0,1]. Тогда моделью посаженного разбиения называется случайный граф, в котором множество вершин есть множество пар ),г € {1,... ,к},] € {1 ,...,щ}, а ребра проводятся независимо с вероятностью р для вершин с совпадающей первой координатой и вероятностью д для вершин с различной первой координатой. При этом вершины (г, 1),... , (г,щ) называются г-тым кластером.

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

Одной из наиболее популярных задач, связанных с моделью посаженного разбиения, является задача о восстановлении исходного разбиения на кластеры по графу со стертыми метками (см., например, [20—24]) . В случае р > д представляется разумным использовать с этой целью алгоритм кластеризации, который бы разбил наш граф на такие подграфы, что они будут являться хорошими приближениями исходных кластеров графа.

Модулярность

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

Определение 5. Разбиением множества вершин графа С = (V, Е) называется множество А = {Ах,..., Ак}, где А{ П А^ = 0, Ах и ... и Ак = V .В дальнейшем тексте мы для краткости будем опускать слова "множества вершин" и говорить, что А — разбиение графа С.

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

^е(А)

АеЛ у '

где е(А) — количество ребер, оба конца которых лежат в А.

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

Определение 7. Степенным штрафом разбиения Л графа С = (V, Е) называется величина

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

Определение 8. Модулярностью разбиения Л графа С = (V, Е) называется величина

Наконец, определим модулярность графа С как максимум из модулярностей его разбиений.

Определение 9. Модулярностью графа С называется величина

Данное определение было впервые введено в статье Ньюмана и Гирвана (см. [25]) . С тех пор эта величина стала ключевой во многих современных алгоритмах кластеризации (см., например, [26—32]) и стала популярным объектом прикладных исследований (см. [33—35]) . К сожалению, максимизация данной величины является КР-трудной задачей (см. [36]) , поэтому представляет интерес теоретическое изучение модулярности (см. [37—40]) . В последние годы было получено множество оценок для различных классов графов, таких как звезды, гиперкубы, графы, удовлетворяюще степенному закону (см. [41]), графы, близкие к полным (см. [42]), деревья с

4е2(У)

д*(С) = тах д(Л).

л

небольшой максимальной степенью (см. [43]), а также большого числа моделей случайных графов. В частности, были получены результаты для различных вероятностных моделей веб-графов, таких как модели предпочтительного присоединения (см. [44, 45]), а также графов С(п,(£) (случайные ^-регулярные графы) (см. [46])и классической модели Эрдеша-Реньи (см. [47]).

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

Клико-хроматические числа

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

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

Прокомментируем это определение. Нетрудно видеть, что клико-хроматическое число графа никогда не превосходит его хроматического числа (то есть минимального числа цветов, в которое можно покрасить граф таким образом, что концы любого ребра будут иметь разные цвета). Однако более сильные оценки на клико-хроматическое число графа в терминах его хроматического числа получить невозможно. Так, для графов без треугольников эти величины совпадают (отдельно заметим, что отсутствие треугольников не накладывает никаких ограничений на хроматическое число графа, см. [48, 49]). В то же время для полного графа хроматическое и клико-хроматическое числа отличаются весьма сильно: хроматическое число с очевидностью равно п, в то время как клико-хроматическое число равно 2 — достаточно взять любую неодноцветную раскраску.

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

Спектр графов

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

Определение 11. Пусть С — ^-регулярный граф на п вершинах, то есть граф, степень каждой вершины которого равна (1. Рассмотрим А — матрицу смежности графа С и найдем все её собственные значения, Л1 ^ ... ^ Лп. Пусть теперь Л = тах{|Л2|,..., |ЛП|}. Тогда будем говорить, что С — (пДЛ)-граф.

Исследование (п,(1, Л)-графов — одно из популярных направлений исследований современной теории графов. Этой теме посвящено большое количество работ в последние несколько десятилетий (см., например, [58—67]).

Обозначения

В настоящей диссертации будут использованы следующие обозначения

— е(С) — количество ребер в графе С.

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

— Ср(п, г, в) — то же, что и С(п, г, в)(р).

— е(У) — количество ребер в графе С, оба конца которых лежат в V.

— е(У,р) — количество ребер в графе С(р), оба конца которых лежат в V.

— е(У, и) количество ребер в графе С, один из концов которого лежит в V, а другой — в и. Ребра из V П и считаются дважды.

— е(У, и,р) — то же самое, но для графа С(р).

— deg(v,p) — степень вершины V в С(р).

— Ус — множество вершин графа С.

— Ес — множество ребер графа С.

— 7 := Ус \ V.

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

Научная новизна: Все результаты данной диссертации получены автором и являются новыми.

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

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

2. Для многих параметров г, в существенно улучшены известные нижние оценки клико-хроматических чисел графов С(п,г,з).

3. Для случая в = г — 1 улучшена верхняя оценка клико-хроматических чисел графов С(п,г,в).

4. Впервые получена верхняя оценка клико-хроматических чисел графов С(п,3,1).

5. Получено точное значение клико-хроматических чисел графов С(п,2,1).

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

7. Аналогичные результаты получены и для случайных подграфов графов Джонсона.

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

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях и научных семинарах:

1. Конференция "Осенние математические чтения в Адыгее" (Майкоп, 2021);

2. Конференция EUROCOMB (Барселона, 2021);

3. Конференция "Графы, Игры и Модели" (Майкоп, 2022);

4. Конференция "Вероятностные методы в дискретной математике" (Петрозаводск, 2024);

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

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

Публикации. Основные результаты по теме диссертации изложены в 9 печатных изданиях, 9 из которых изданы в журналах, рекомендованных ВАК, 9 —в периодических научных журналах, индексируемых Web of Science и Scopus.

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

Глава 1. Клико-хроматические числа графов Джонсона

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

Первые оценки клико-хроматических чисел графов Джоносна были получены в 2019 году в работе [50]. Для их формулировки нам потребуется дать определение чисел Рамсея.

Определение 12. Числом Рамсея Яа(Ь,д) называется минимальное значение N, при котором для любой раскраски ребер а-однородного гиперграфа на N вершинах в д цветов найдется полный подграф на Ь вершинах, все ребра которого имеют один и тот же цвет.

В вышеупомянутой работе были доказаны следующие теоремы.

Теорема 1 ([50]).

а) Пусть в = 0,п ^ г(г + 1), тогда Хс(0(п, г, в)) = 2.

б) Пусть з > 0, тогда для любого д удовлетворяющего условию п ^ Яг(з + (г — з)(г — з + 1),д) выполняется неравенство Хс(0(п,г,з)) > д.

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

Теорема 2 ([50]). Пусть п < Яг(г + 1,д — г — 1). Тогда Хс(0(п, г, г — 1)) ^ д.

Данная теорема показывает, что оценка из теоремы 1 действительно разумна, по крайней мере, для г = з + 1.

1.2 Новые результаты

Сформулируем новые оценки, полученные нами в работах [82—84] для клико-хроматических чисел графов Джонсона.

Первые две доказанные теоремы улучшают результат теоремы 2.

Теорема 3. Если п > 2, то Хс(0(п,2,1)) = шт{д е N : п < Я2(3,д)}.

Теорема 4. Если п > г > 2 и 2г — 1 ^ п < Яг(г + 1,д — 2), то Хс(0(п,г,г — 1)) ^ д.

Сравним результаты теорем 4 и 2. Может показаться, что улучшение не слишком существенно, поскольку параметр количества цветов изменяется лишь на константу. Однако, как будет следовать из сформулированных далее утверждерний, даже такое небольшое изменение параметра серьезно влияет на асимптотику.

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

Определение 13. Назовем гиперграф на 7 вершинах с множеством ребер

раскраске ребер полного 3-однородного гиперграфа на N вершинах в д цветов

Я3(7,д), то есть функция определена корректно). Теперь мы готовы сформулировать теорему.

Теорема 5. Пусть п > 8. Тогда

1. если п ^ ЯА(д), то Хс(0(п,3,1)) > д.

2. если п < ЯА(д — 2), то Хс(0(п,3,1)) ^ д.

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

Теорема 6. Пусть г — в = 2к + 1,п > г > 8 > 0. Тогда для любого д, такого

(123) (145) (16 7) 7) (2 47) (346) (2 5

гиперграфом типа треугольник.

Определение 14. Определим ЯА(д) как минимальное такое N, что в любой

найдется одноцветный подграф типа треугольник. (Очевидно, что ЯА(д) ^

+

Отметим, что в силу неравенства в+(г—в)(г—5+1) ^ {г—з+1){г—8+2) + 1) (причем равенство достигается лишь в случае г — в = 1), а также монотонности Яа(Ь,д) по Ь данная теорема, очевидно, сильнее теоремы 1.

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

Теорема 7. Пусть к > 0,п > 4к + 2, в = 2к + 1,г = 4к + 2. Тогда для любого д, такого что п ^ зЯ2(3,д), выполняется неравенство Хс(0(п,г,з)) > д.

Сравним указанные теоремы. В [68] была доказана следующая нижняя оценка чисел Рамсея.

Теорема 8 ([68]). При а ^ Ъ,д ^ 3 верно неравенство Яа(Ь,д) — 1 ^

2Яа- 1(Ь—2,д) — 1.

Замечание. Отметим, что существуют и верхние оценки чисел Рамсея, см, например, теорему 1 из [69].

Используем эту теорему для сравнения теорем. Теорема 6 гласит, что, коль скоро п ^ Я4к+2 (2к2 + 7к + 3,д), то выполняется неравенство Хс(0(п,г,з)) > д. Теорема 7 утверждает то же неравенство в условиях п ^ (2к — 1)Я2(3,д). Из тривиальных оценок чисел Рамсея имеем, что теорема 7 позволяет доказать неравенство Хс(0(п,г,з)) > д (как минимум) при п ^ (2к — 1)^. В то же время, из теоремы 8 легко понять, что

. о ч о П4(2к2-к+7,д)-1

ЯАк+2 (2к2 + 7к + 3,д) — 1 ^ 2 ,

где башня из 2 имеет высоту 4к — 2. Отсюда при помощи вероятностного метода тривиально получается оценка

/ о \ о к 1о82 9

Я4к+2 (2к2 + 7к + 3,д) ^ 2 ,

что, конечно, существенно хуже оценки из теоремы 7.

Наконец, сформулируем теорему, которая позволяет получить существенно более сильные оценки Хс(0(п,г,з)) для целого ряда параметров г, з.

Теорема 9. Пусть п > г > s, а р £ P, где P — множество простых чисел. Пусть также а, к £ N удовлетворяют следующим соотношениям: s ^ к, г — s = рак и к mod ра > Ра . Тогда для любого q, такого что

п ^ kRpa+i(p2a + ра + l,q) + (s — k),

верно неравенство Xc(G(n,r, s)) > q.

Сравним этот результат с теоремой 1 на примере случая г — з = рт,в ^ р- - -. Возьмем к = р-"-"-1, а = [_|, тогда все условия теоремы 9 выполняются. Это дает следующую нижнюю оценку величины Хс^(п,г, й)) :

Если

п ^ р-т--Я -ш+2- ^ (р2-т+2- + р-т+2- + 1,^) + (в — р-,

то Хс(0(п,г,з)) > q.

В случае использования теоремы 1 мы получим другую оценку этой же величины: если п ^ Яг(в + (г — в)(г — в + 1)^) = Яг(г + р2т^), то Хс{0(п, г, в)) > q.

Докажем теперь, что первая оценка существенно лучше второй. Для этого мы покажем, что

Я -™+2- ^ (р2-+ р-+ 1,д) ^ Яг(г + р2т,я).

Последовательно применяя теорему 8 г — ра — 1 раз, мы получаем, что

2Пра+1(г+р2т-2г+2ра+2,ч)-1

Яг(г + р2т^) ^ 22"' .

Для г + р2т — 2г + 2ра + 2 > р2а + ра + 1, или, что то же самое, г < р2т—р2а+ра+1 мы имеем Ярк+1(г+р2т—2г+2ра+2, д) — 1 ^ Яр*+1 (р2а+ра+1, q), откуда очевидно, что оценки из теоремы 9 куда сильнее аналогичных оценок, получаемых при помощи теоремы 1.

Оставшая часть данной главы посвящена доказательству приведенных выше результатов. В разделе 1.3.1 доказаны нижние оценки клико-хроматических чисел графов С(п,г,г — 1) (теоремы 3 и 4). Раздел 1.3.2 посвящен случаю С(п, 3,1) (теорема 5). Наконец, в разделе 1.3.3 приведены доказательства верхних оценок для различных семейств графов (теоремы 6, 7 и 9).

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

Прежде чем переходить к доказательству теорем, укажем некоторые обозначения, используемые в них, а также дадим комментарии, необходимые для лучшего понимания этих доказательсты. Так, под обозначением 1(5'),5 С {1,... ,п} будет пониматься вектор, ¿-тая координата которого равна 1 тогда и только тогда, когда г Е 5 (и равна 0 в противном случае). Помимо этого, мы будем использовать обозначения [а, Ь] и [Ь] для множества целых чисел, лежащих на отрезках [а,Ь] и [1,Ь] соответственно. Также стоит отметить, что в разделах 2 и 3 мы будем отождествлять вершины графов Джонсона с подмножествами множества [п], в то время как в разделе 4 мы будем работать с вершинами как с векторами из {0,1}п.

1.3.1 Доказательство нижних оценок

Доказательство теоремы 3. В силу теоремы 1 достаточно доказать, что при п < Я2(3,д) имеет место неравенство Хс(^(п,2,1)) ^ д. Доказывать это утверждение будем при п > 3, для п = 3 оно тривиально. Заметим сначала, что граф С(п, 2,1) содержит максимальные клики двух типов: клики размера три, имеющие вид {(г,]), (],к), (к,г)} для некоторых г,], к (такие клики назовем кликами первого типа) и клики, состояшие из всех пар вида (10/1), где г пробегает все значения от 1 до п, за исключением г0 (такие клики будем называть кликами второго типа, а соответствующие г0 будем называть общими элементами таких клик).

В силу того, что п < Я2(3,д), существует раскраска вершин С(п, 2,1), в которой отсутствуют одноцветные клики первого типа (для этого достаточно рассмотреть раскраску ребер графа Кп, не содержащую одноцветных треугольников, а затем положить цвет вершины (г,]) в графе С(п, 2,1) равным цвету ребра (г,]) в графе Кп). Теперь заметим, что в такой раскраске присутствует не более одной одноцветной клики второго типа. Действительно, пусть нашлось две одноцветные клики с общими элементами г и ] соответственно. Рассмотрим произвольный к = г,] и заметим, что цвета

вершин (к,г), (г,]) и (],к) равны. Но тогда эта тройка образует одноцветную клику первого типа, которой, по построению раскраски, не существует.

Остается рассмотреть случай, когда нашлась ровно одна одноцветная клика второго типа. Без ограничения общности будем считать, что ее общий элемент равен 1, а ее цвет с1. Рассмотрим вершины (2,3), (3, 4), (4, 2). Поскольку это клика первого типа, то у двух из этих вершин разные цвета. Пусть, для определенности, это вершины (2,3) и (3,4), а их цвета равны, соответственно, с2 и с3. Отметим, что ни один из этих цветов не может быть равен с1, иначе имеем одноцветную клику первого типа. Тогда перекрасим вершину (1,3) в цвет с2. Проверим, что все максимальные клики теперь неодноцветны. Очевидно, что любая клика, не содержащая перекрашенную вершину, осталась неодноцветной, рассмотрим теперь клики, содержащие ее. Начнем с клик первого типа. Заметим, что они имеют вид {(1,г), (г, 3), (3,1)}, но тогда они содержат, как минимум, цвета с1 (цвет вершины (1,г)) и с2 (цвет вершины (1,3)). Теперь рассмотрим клики второго типа. Клика с общим элементом 1 неодноцветна из тех же соображений, что и клики первого типа, а клика с общим элементом 3 содержит вершины (1, 3) и (3,4), цвета которых не равны. □

Доказательство теоремы 4. Начнем, как и в прошлой теореме, с описания

всевозможных максимальных клик в С(п,г,г — 1). Нетрудно видеть, что

макисмальные клики таких графов имеют один из двух типов: клики вида / X \

(г), \Х| = г + 1, где под этим обозначением понимаются всевозможные г-элементные подмножества множества X, и клики, имеющие вид {У и {г}}1фу, \ = г — 1. По аналогии с предыдущей теоремой будем называть эти клики кликами первого и второго типа соответственно.

В силу п<Кг(г + 1,д — 2) мы можем покрасить наш граф в д — 2 цвета таким образом, что все клики первого типа будут неодноцветными. Разберемся теперь с одноцветными кликами второго типа. Для этого рассмотрим все вершины, содержащие единицу. Покрасим такие вершины в цвет д — 1, если сумма чисел, соответствующих этой вершине, четна, и в цвет д в противном случае.

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

с номером цвета, не превосходящим д—2 (то есть не содержащая единицу), так и хотя бы одна вершина цвета д — 1 или д (соответственно, вершина, содержащая единицу). Теперь рассмотрим клики второго типа. Если единица не входит в У такой клики, то, как и в прошлом случае, в клике содержится как вершина д — 1 или д, так и вершина одного из других (д — 2)-х цветов. Если же 1 входит в У такой клики, то, в силу условия п ^ 2г — 1, среди п — г + 1 числа, не входящего в У, найдутся числа разной четности, а тогда в данной клике будут как вершины цвета д — 1, так и вершины цвета д. □

1.3.2 Случай г = 3,в = 1

Доказательство теоремы 5. Классифицируем все максимальные клики в С(п,3,1). Пусть есть число с, входящее хотя бы в 4 вершины некоторой максимальной клики. Тогда у любой вершины, не содержащей с, должно быть непустое пересечение с 4 непересекающимися двухэлементными множествами, что, очевидно, невозможно, так как в каждой вершине всего 3 элемента. Но тогда все вершины клики имеют вид (с, а, вк), где множества {а, вк} попарно непересекаются. Так как клика максимальная, то объединение всех ак, в к имеет размер п — 1 или п — 2. Такие клики мы будем называть кликами типа звезда (а вершину с - её центром). Пусть наша клика не является кликой типа звезда, тогда любое число присутствует в ее вершинах не более трех раз. Пусть некоторое число с встречается ровно в трех вершинах, тогда любая другая вершина в клике вкладывается в объединение трех вершин, то есть вся клика изоморфна некоторой максимальной клике в С(7,3,1). Нетрудно проверить, что в этом графе все максимальные клики изоморфны графу типа треугольник (то есть индуцированному подграфу С(7,3,1), вершины которого совпадают с ребрами гиперграфа типа треугольник). Также легко видеть, что клика типа треугольник действительно является максимальной в С(п,3,1) при любом п. Осталось разобраться со случаем, когда каждое число содержится не более чем в двух вершинах. Рассмотрим любую вершину такой клики. Она пересекается с каждой другой вершиной клики ровно по одному элементу, причем все эти элементы попарно различны. Но тогда в максимальной клике не более четырех вершин. Случаи, когда вершин 1 или 2, очевидны (можем вложить их в клику

типа звезда). Пусть % — элемент, по которому пересекаются вершины 1 и 2. Если вершины 3, то рассмотрим элемент у из третьей вершины, не содержащийся в первых двух. Очевидно, что {%,]} пересекается с каждой из трех вершин по 1 элементу. Осталось взять в качестве третьего элемента любой, не содержащийся в объединении этих трех вершин (это можно сделать, так как п > 8). Для случая четырех вершин просто возьмем в качестве ] элемент, по которому пересекаются 3 и 4 вершины, далее рассуждения аналогичны.

Таким образом, любая максимальная клика в С(п,3,1),п > 8 либо являются кликой типа звезда, либо кликой типа треугольник. Это доказывает первую часть теоремы.

Теперь докажем вторую часть: покрасим С(п,3,1) в д — 2 цвета так, чтобы не было одноцветной клики типа треугольник. После этого перекрасим некоторые вершины нашего графа следующим образом: пусть <Л(у) = \{ 1,2,3} П у\. Тогда, если ¿(у) = 1, то перекрасим её в цвет д — 1, если ¿(у) ^ 2, то в цвет д, иначе оставим все как есть. Докажем, что не будет существовать одноцветных клик типа звезда. Действительно, рассмотрим 2 случая: если центр звезды лежит в {1,2,3}, то в клике будет существовать вершина, содержащая одно из оставшихся чисел из этого множества, но таких вершин будет не более двух. Тогда в множестве будут присутствовать как вершины цвета д, так и вершины цвета д—1. Доказательство для второго случая полностью аналогично. Осталось рассмотреть клики типа треугольник. Любая одноцветная клика типа треугольник должна быть цвета д или д — 1. Пусть она цвета д. Тогда каждая вершина клики содержит хотя бы 2 из чисел 1,2,3. Но тогда пересекаются любые две вершины тоже по числу из этого множества, то есть всего чисел, которые принадлежат хотя бы двум вершинам, не более трех. Противоречие. Отсюда любая одноцветная клика имеет цвет д — 1. Пусть Е - множество элементов, присутствующих хотя бы в одной вершине нашей клики. Заметим, что для любых двух элементов Е верно, что в клике есть вершина, содержащая их. Отсюда \Е П {1,2,3}\ = 1. Но тогда в клике найдется вершина, не содержащая этот элемент, а, значит, одноцветных клик типа треугольник также не может существовать. □

Список литературы диссертационного исследования кандидат наук Кошелев Михаил Михайлович, 2024 год

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

[1] J. Kahn и G. Kalai. — «A counterexample to Borsuk's conjecture». — В: Bulletin (new series) of the AMS 29:1.29 (1993), с. 60—62.

[2] P. Frankl и R. Wilson. — «Intersection theorems with geometric consequences». — В: Combinatorica 1 (1981), с. 357—368.

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

[4] A.M. Raigorodskii. — «Around Borsuk's conjecture». — В: J. of Math. Sci. 154:4 (2008), с. 604—623.

[5] A.M. Raigorodskii. — «The Borsuk partition problem: the seventieth anniversary». — В: Mathematical Intelligencer 26:3 (2004), с. 4—12.

[6] A.M. Raigorodskii. — «Three lectures on the Borsuk partition problem». — В: London Mathematical Society Lecture Note Series 347 (2007), с. 202—248.

[7] A. Sagdeev и A. Raigorodskii. — «On a Frankl-Wilson theorem and its geometric corollaries». — В: Acta Mathematica Universitatis Comenianae 88(3) (2019), с. 1029—1033.

[8] F. J. MacWilliams и N. J. A. Sloane. — «The theory of error-correcting codes». — В: (1977).

[9] Tuvi Etzion. — «On the Nonexistence of Perfect Codes in the Johnson Scheme». — В: SIAM Journal on Discrete Mathematics 9.2 (1996), с. 201—209.

[10] J. Balogh, D. Cherkashin и S. Kiselev. — «Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs». — В: European Journal of Combinatorics 79C (2019), с. 228—236.

[11] А.Б. Купавский и А.А. Сагдеев. — «Теория Рамсея в пространстве с чебышeвской метрикой». — В: УМН 75:5 (2020), с. 191—192.

[12] S. Kiselev и A. Kupavskii. — «Sharp bounds for the chromatic number of random Kneser graphs». — В: Acta Mathematica Universitatis Comenianae 88(3) (2019), с. 861—865.

[13] A. Kupavskii. — «Random Kneser graphs and hypergraphs». — В: Electron. J. Comb. 25, N4 (2018).

[14] Ф.А. Пушняков и А. М. Райгородский. — «Оценка числа ребер в особых подграфах некоторого дистанционного графа». — В: Матем. заметки 107:2 (2020), с. 322—332.

[15] Ф.А. Пушняков и А. М. Райгородский. — «Оценка числа ребер в подграфах графа Джонсона». — В: Докл. РАН. Матем., информ., проц. упр. 499 (2021), с. 40—43.

[16] M. M. Pyaderkin. — «On the chromatic number of random subgraphs of a certain distance graph». — В: Discrete Appl. Math. 267 (2019), с. 209—214.

[17] Louis Anthony Agong и др. — «On the girth and diameter of generalized Johnson graphs». — В: Discrete Mathematics 341.1 (2018), с. 138—142.

[18] John S. Caughman, Ari J. Herman и Taiyo S. Terada. — «The odd girth of generalized Johnson graphs». — В: Discrete Mathematics 347.7 (2024), с. 113985.

[19] P. J. Bickel и A. Chen. — «A nonparametric view of network models and Newman-Girvan and other modularities». — В: Proc. Nat. Acad. Sci. India Sect. A 106.21068 (2009).

[20] E. Abbe и C. Sandon. — «Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery». — В: IEEE 56th Annual Symposium on Foundations of Computer Science 79C (2015), с. 670—688.

[21] J. Lei и A. Rinaldo. — «Consistency of spectral clustering in stochastic block models». — В: Ann. Statist. 43.1 (2015), с. 215—237.

[22] Anne Condon и Richard M. Karp. — «Algorithms for graph partitioning on the planted partition model». — В: Random Structures & Algorithms 18.2 (2001), с. 116—140.

[23] Debapratim Banerjee. — «Contiguity and non-reconstruction results for planted partition models: the dense case». — В: Electronic Journal of Probability 23.none (2018), с. 1—28. — URL: https://doi.org/10.1214/17-EJP128.

[24] Shubham Gupta h Ambedkar Dukkipati. — «Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions». — B: Advances in Neural Information Processing Systems 35 (2022). nog peg. S. Koyejo h gp., c. 13527—13540.

[25] M. E. J. Newman h M. Girvan. — «Finding and evaluating community structure in networks». — B: Phys. Rev. 69 (2004), c. 26—113.

[26] K. Avrachenkov h gp. — «PageRank in Undirected Random Graphs». — B: Internet Math. (2017). — URL: http://www.internetmathematicsjournal.com/ article/1625-pagerank-in-undirectedrandom-graphs.

[27] A. Clauset, M.E.J. Newman h C. Moore. — «Finding community structure in very large networks». — B: Phys. Rev. E 70, 066111 (2006).

[28] A.V. Gasnikov h gp. — «About the power law of the pagerank vector component distribution. Part 1. Numerical methods for finding the pagerank vector». — B: Numerical Analysis and Applications 10, 4 (2017), c. 299—312.

[29] A.V. Gasnikov h gp. — «About the power law of the pagerank vector component distribution. Part 2. The Buckley-Osthus model, verification of the power law for this model, and setup of real search engines». — B: Numerical Analysis and Applications 11,1 (2018), c. 16—32.

[30] P. Miasnikof h gp. — «A Statistical Test of Heterogeneous Subgraph Densities to Assess Clusterability». — B: Learning and Intelligent Optimization. — nog peg. N. Matsatsinis, Y. Marinakis h P. Pardalos. — Springer, 2020.

[31] G. Agarwal h D. Kempe. — «Modularity-maximizing graph communities via mathematical programming». — B: The European Physical Journal B 66.3 (2008), c. 409—418.

[32] Rafael Santiago h Luis C. Lamb. — «Efficient modularity density heuristics for large graphs». — B: European Journal of Operational Research 258.3 (2017), c. 844—865. — URL: https://www.sciencedirect.com/science/article/pii/ S0377221716308670.

[33] Roger Guimera, Marta Sales-Pardo h Luis A. Nunes Amaral. — «Modularity from fluctuations in random graphs and complex networks». — B: Phys. Rev. E 70 (2 2004), c. 025101. — URL: https://link.aps.org/doi/10.1103/PhysRevE. 70.025101.

[34] Sergio Antonio Alcala-Corona и др. — «Modularity in Biological Networks». — В: Frontiers in Genetics 12 (2021). — URL: https://www.frontiersin.org/ journals/genetics/articles/10.3389/fgene.2021.701331.

[35] Dirk M. Lorenz, Alice Jeng и Michael W. Deem. — «The emergence of modularity in biological systems». — В: Physics of Life Reviews 8.2 (2011), с. 129—160. — URL: https://www.sciencedirect.com/science/article/pii/ S1571064511000170.

[36] Ulrik Brandes и др. — «On Modularity — NP-Completeness and Beyond». — В: (2006). — URL: https://core.ac.uk/reader/197562950.

[37] Baptiste Louf, Colin McDiarmid и Fiona Skerman. — «Modularity and Graph Expansion». — В: 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs) 287 (2024). Под ред. Venkatesan Guruswami, 78:1—78:21. — URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.78.

[38] Dario Fasino и Francesco Tudisco. — «An Algebraic Analysis of the Graph Modularity». — В: SIAM Journal on Matrix Analysis and Applications 35.3 (2014), с. 997—1018.

[39] Fabien de Montgolfier, Mauricio Soto и Laurent Viennot. — «Asymptotic Modularity of Some Graph Classes». — В: Algorithms and Computation (2011). Под ред. Takao Asano и др., с. 435—444.

[40] Jordan Chellig, Nikolaos Fountoulakis и Fiona Skerman. — «The modularity of random graphs on the hyperbolic plane». — В: Journal of Complex Networks 10.1 (2021), cnab051.

[41] F. De Montgolfier, M. Soto и L. Viennot. — «Asymptotic modularity of some graph classes.» — В: Algorithms and Computation (2011), с. 435—444.

[42] S. Trajanovski, H. Wang и P. Van Mieghem. — «Maximum modular graphs». — В: The European Physical Journal B-Condensed Matter and Complex Systems 85.7 (2012), с. 1—14.

[43] C. McDiarmid и F. Skerman. — «Modularity of regular and treelike graphs». — В: J. Complex Netw. 6 (2018), с. 596—619.

[44] L. Ostroumova Prokhorenkova, P. Pralat и A. Raigorodskii. — «Modularity in several random graph models». — В: Electronic Notes in Discrete Mathematics 61 (2017), с. 947—953.

[45] L.N. Iskhakov h gp. — «Clustering Coefficient of a Spatial Preferential Attachment Model». — B: Doklady Mathematics 98 (1) (2018), c. 304—307.

[46] B. Bollobas. — «The isoperimetric number of random regular graphs». — B: Europ. J. Combinatorics 9 (1988), c. 241—244.

[47] C. McDiarmid h F. Skerman. — «Modularity of Erdos-Renyi random graphs». — B: Random Structures & Algorithms 57 (2020), c. 211—243.

[48] W. Tutte. — «Solution to Advanced Problem no. 4526». — B: The American Mathematical Monthly 61 (1954), c. 352.

[49] P. Erdos. — «Graph theory and probability». — B: Canadian Journal of Mathematics 11 (1959), c. 34—38.

[50] D. A. Zakharov h A. M. Raigorodskii. — «Clique-chromatic numbers of graphs of intersections». — B: Math. Notes 105 (2019), c. 138—140.

[51] N. Alon h M. Krivelevich. — «Clique coloring of dense random graphs». — B: J. Graph Theory 88 (2018), c. 428—433.

[52] D. Defossez. — «Clique-coloring some classes of odd-hole-free graphs». — B: J. Graph Theory 53 (2006), c. 233—249.

[53] J. Fox, J. Pach h A. Suk. — «A note on the clique chromatic number of geometric graphs». — B: Geombinatorics 28 (2018), c. 83—86.

[54] M. R. Cerioli h A. L. Korenchendler. — «Clique-coloring circular arc graphs». — B: Electron. Notes Discret. Math. 35 (2009), c. 287—292.

[55] G. Joret h gp. — «Tight Bounds on the Clique Chromatic Number». — B: Electron. J. Comb. 28, N3 (2021).

[56] N. Alon h M. Krivelevich. — «Clique coloring of dense random graphs». — B: Journal of Graph Theory 88:3 (2017), c. 428—433.

[57] Yu. Demidovich h M. Zhukovskii. — «Tight asymptotics of clique-chromatic numbers of dense random graphs». — B: Journal of Graph Theory 103:3 (2023), c. 251—261.

[58] N. Alon h V.D. Milman. — «Ai, isoperimetric inequalities for graphs and superconcentrators». — B: J. Combin. Theory Ser. B 38 (1985), c. 73—88.

[59] M. Krivelevich h B. Sudakov. — «Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs». — B: More sets, graphs and numbers, Bolyai Society Mathematical Studies (2006), c. 199—262.

[60] Noga Alon, Michael Krivelevich и Benny Sudakov. — «List Coloring of Random and Pseudo-Random Graphs». — В: Combinatorica 19 (1999), с. 453—472.

[61] Xiaofeng Gu. — «Toughness in pseudo-random graphs». — В: European Journal of Combinatorics 92 (2021), с. 103255.

[62] Alan Frieze, Michael Krivelevich и Ryan Martin. — «The emergence of a giant component in random subgraphs of pseudo-random graphs». — В: Random Structures & Algorithms 24 (2003), с. 42—50.

[63] David Conlon, Jacob Fox и Yufei Zhao. — «Extremal results in sparse pseudorandom graphs». — В: Advances in Mathematics 256 (2014), с. 206—290. — URL: https://www.sciencedirect.com/science/article/pii/ S0001870813004507.

[64] Rajko Nenadov. — «Triangle-factors in pseudorandom graphs». — В: Bulletin of the London Mathematical Society 51.3 (2019), с. 421—430. — URL: https: //londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms.12237.

[65] N. Alon и др. — «Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs». — В: IEEE Transactions on Information Theory 38.2 (1992), с. 509—516.

[66] Jie Han, Yoshiharu Kohayakawa и Yury Person. — «Near-perfect clique-factors in sparse pseudorandom graphs». — В: Electronic Notes in Discrete Mathematics 68 (2018). Discrete Mathematics Days 2018, с. 221—226. — URL: https://www.sciencedirect.com/science/article/pii/S157106531830129X.

[67] Xizhi Liu, Dhruv Mubayi и David Munha Correia. — «Turan problems in pseudorandom graphs». — В: Combinatorics, Probability and Computing (2024), с. 1—14.

[68] D. Conlon, J. Fox и B. Sudakov. — «An improved bound for the stepping-up lemma». — В: Discrete Applied Mathematics 161 (2013), с. 1191—1196.

[69] P. Erdos и R. Rado. — «Combinatorial theorems on classifications of subsets of a given set». — В: Proceedings of the London Mathematical Society 3 (1952), с. 417—439.

[70] А. Р. Ярмухаметов. — «О связности случайных дистанционных графов специального вида». — В: Чебышевский сборник 10(1) (2009), с. 95—108.

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

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

[73] M.M. Ipatov. — «Exact modularity of line graphs of complete graphs». — В: Moscow Journal of Combinatorics and Number Theory 10(1) (2021), с. 61—75.

[74] L. Ostroumova Prokhorenkova, P. Pralat и A. Raigorodskii. — «Modularity of Complex Networks Models». — В: In International Workshop on Algorithms and Models for the Web-Graph; Springer: Berlin (2016), с. 115—126.

[75] P. Delsart. — «An algebraic approach to the association schemes of coding theory». — В: Philips Res. Repts. Suppl. 10 (1973).

[76] L. Lovasz. — «On the Shannon capacity of a graph». — В: IEEE Transactions on Information Theory 14 (1979), с. 1—7.

[77] A. E. Brouwer и др. — «The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters». — В: J. Combin. Theory Ser. B 133 (2018), с. 88—121.

[78] W. Hoeffding. — «Probability Inequalities for Sums of Bounded Random Variables». — В: Journal of the American Statistical Association 58(301) (1963), с. 13—30.

[79] P. Erdos и A. Renyi. — «On random graphs». — В: I, Publ. Math. Debrecen 6 (1959), с. 290—297.

[80] A. Frieze, M. Krivelevich и R. Martin. — «The emergence of a giant component in random subgraphs of pseudo-random graphs». — В: Random Structures & Algorithms 24(1) (2004), с. 42—50.

[81] Y. Alon и M. Krivelevich. — «Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs». — В: SIAM Journal on Discrete Mathematics 36 (2022), с. 728—754.

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

[82] M. Koshelev. — "Lower bounds on the clique-chromatic numbers of some distance graphs". — In: Moscow Journal of Combinatorics and Number Theory 10.2 (2021), p. 141—148.

[83] A. Raigorodskii and M. Koshelev. — "New bounds on clique-chromatic numbers of Johnson graphs". — In: Discrete Applied Mathematics 283 (2020), p. 724—729.

[84] А.М. Райгородский и М.М. Кошелев. — «Новые оценки клико-хроматических чисел графов Джонсона». — В: Доклады Российской академии наук. Математика, информатика, процессы управления 490.1 (2020), с. 78—80.

[85] М.М. Ипатов, М.М. Кошелев и А.М. Райгородский. — «Модулярность некоторых дистанционных графов». — В: Доклады Российской академии наук. Математика, информатика, процессы управления 490.1 (2020), с. 71—73.

[86] M. Ipatov, M. Koshelev, and A. Raigorodskii. — "New bounds on clique-chromatic numbers of Johnson graphs". — In: European Journal of Combinatorics 117.2 (2024), p. 103833.

[87] Н.М. Деревянко и М.М. Кошелев. — «Новые оценки модулярности графов G(n,r, s) и Gp(n,r, s)». — В: Проблемы передачи информации 57.4 (2021), с. 87—109.

[88] M. Koshelev. — "New lower bound on the modularity of Johnson graphs". — In: Moscow Journal of Combinatorics and Number Theory 10.1 (2021), p. 77—82.

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

[90] M. Koshelev. — " Modularity in planted partition model". — In: Computational Management Science 20.34 (2023).