Числа независимости и хроматические числа случайных дистанционных графов Пядеркин Михаил Михайлович

Короткий опис

Пядеркин, Михаил Михайлович.
Числа независимости и хроматические числа случайных дистанционных графов : диссертация ... кандидата физико-математических наук : 01.01.05 / Пядеркин Михаил Михайлович; [Место защиты: Моск. физ.-техн. ин-т (гос. ун-т)]. - Москва, 2019. - 79 с.
Оглавление диссертациикандидат наук Пядеркин Михаил Михайлович
1.1 Граф G(n, 3,1)
1.2 Случайные графы в модели Эрдеша-Реньи
1.3 Формулировки результатов
1.4 Числа независимости
1.4.1 Доказательство теоремы
1.4.2 Нижняя оценка
1.4.3 Оптимальная верхняя оценка
1.5 Хроматическое число
1.5.1 Блоки и раскраски блоков
1.5.2 Раскраска троек, пересекающих множества I и J
1.5.3 Разделяй и властвуй
2 Число независимости и хроматическое число случайного подграфа G(n,r,s)
2.1 Введение и формулировки результатов
2.2 Числа независимости
2.2.1 Верхняя оценка с помощью стандартного метода
2.2.2 Граф G(n, 2,1)
2.2.3 Кнезеровский граф G(n,r, 0)
2.2.4 Общая теорема о числе независимости
2.2.5 Доказательство вспомогательных утверждений
2.3 Хроматическое число случайного графа G/2(n,r,s)
2.3.1 Доказательство теоремы
3 Устойчивость независимых множеств
3.1 Введение и формулировки результатов
3.2 Устойчивость в графе G/2(n,r, < s)
3.3 Устойчивость независимых множеств G(n,r, 1)
3.3.1 Доказательство теоремы
3.3.2 Предварительные определения для теорем 3.1.8 и
3.3.3 Устойчивость в графе С(и,г, 1), г >
3.3.4 Устойчивость в графе С(и,г, 1), г =
3.3.5 Доказательство вспомогательных лемм
3.4 Пороговая вероятность для асимптотической устойчивости
3.4.1 Доказательство теоремы
Заключение