Задачи о раскрасках разряженных гиперграфов Хузиева Алина Эдуардовна

Краткое описание

Хузиева, Алина Эдуардовна.
Задачи о раскрасках разреженных гиперграфов : диссертация ... кандидата физико-математических наук : 01.01.09 / Хузиева Алина Эдуардовна; [Место защиты: Московский физико-технический институт (национальный исследовательский университет)]. - Москва, 2019. - 83 с.
Оглавление диссертациикандидат наук Хузиева Алина Эдуардовна
1.2 Новые результаты
1.3 Основные инструменты доказательства
1.4 Доказательство теоремы
1.4.1 Построение случайной раскраски
1.4.2 Построение дерева зависимостей
1.4.3 Анализ первого этапа процесса перекраски
1.4.4 Анализ второго этапа перекраски
1.4.5 Анализ возникновения большого числа изменений цветов
1.4.6 Выбор параметров и завершение доказательства
1.5 Дополнение
2 Онлайн предписанное хроматическое число гиперграфов
2.1 Определения
2.2 История задачи о раскрасках полных многодольных
графов и гиперграфов
2.3 Основной результат
2.4 Экстремальные задачи о раскрасках гиперграфов
2.4.1 Связь с задачей о свойстве В
2.4.2 Онлайн аналоги задачи о свойстве В
2.4.3 Новые результаты в экстремальной задаче об онлайн раскрасках
2.5 Доказательства
2.5.1 Доказательство леммы
2.5.2 Доказательство леммы
2.5.3 Доказательство теоремы
2.5.4 Доказательство леммы
3 Сильные раскраски 4-однородных гипеграфов
3.1 Основные определения и изучаемая модель
3.2 История результатов
3.3 Новый результат
3.4 Доказательство теоремы
3.4.1 Точная пороговая вероятность
3.4.2 Равномерная модель
3.4.3 Сбалансированная раскраска
3.4.4 Вычисление первого и второго моментов
3.5 Доказательство леммы
3.5.1 Анализ различных вариантов: хорошие строчки
3.5.2 Анализ различных вариантов: нормальные строчки
3.5.3 Анализ различных вариантов: плохие строчки
3.5.4 Анализ различных вариантов: перебор случаев
3.6 Приложение
Заключение
Список цитируемой литературы
Список работ автора по теме диссертации
Введение