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

• Ахмеджанова Маргарита Булатовна
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Ахмеджанова Маргарита Булатовна

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

1.2 Основной результат первой главы

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

1.3.1 Конструкция Н

1.3.2 Локальная лемма

1.3.3 Анализ плохих событий

1.4 Следствия

1.4.1 Максимальная степень

1.4.2 Число ребер

2 Справедливые раскраски в два цвета

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

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

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

2.3.1 Гиперграфы с малым числом вершин

2.3.2 Вспомогательные неравенства

2.3.3 Алгоритм построения правильной раскраски из случайной раскраски

2.3.4 Анализ ситуаций, в которых не получается правильной раскраски

2.3.5 Построение из правильной раскраски справедливой

2.3.6 Завершение доказательства

3 Справедливые раскраски в г

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

3.2 Основной результат третьей главы

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

3.3.1 Гиперграфы с небольшим числом вершин

3.3.2 Построение правильной раскраски

3.3.3 Анализ алгоритма

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

к

3.3.5 Результаты работы алгоритма

3.3.6 Вспомогательные утверждения о размерах цветовых классов

3.3.7 Построение сбалансированной раскраски

3.3.8 Доказательство существования подмножеств Wi

к

3.3.10 Завершение доказательства теоремы

Заключение

Литература

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

Введение

Актуальность темы исследования

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

Актуальность темы диссертации, несомненно, обусловлена ее приложениями ко многим практическим задачам. Раскраски гиперграфов находят применения в задачах планирования и управления [ , ], в некоторых аспектах эпидемиологии и биологии [ ], в теории кодирования [ ] и во многих других областях. Возникающие в приложениях гипегра-фы часто имеют специальную структуру. Например, в теории кодирования это однородные гиперграфы, в которых любые два гиперребра

Ь

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

Приведем ряд необходимых определений и обозначений. Гиперграфом Н называется пара Н = (V, Е), где V — некоторое множество, называемое множеством вершин, аЕ - произвольная совокупность подмножеств множества V, называемых гиперребрами. Данное определение было вве-

депо Бержем [ ], им же были поставлены многие задачи теории гиперграфов естественные обобщения задач из теории графов на случай гиперграфов.

Степень ребра А Е Е в гиперграфе Н есть число других гиперребер гиперграфа Н, имеющих с А хотя бы одну общую вершину. Максимальная степень гиперребра в Н будет обозначаться через А(Н). Гиперграф называется п-однородным, если каждое гиперребро содержит в точности п вершин. Заметим, что в частном случае п = 2 мы получаем классическое определение графа без петель и кратных ребер. Гиперграф называется Ъ-простым, если в нем любые два разных гиперребра имеют не более Ъ общих вершин. Ъ-иростые гиперграфы хорошо известны в мировой литературе как частичные системы, Штейнера [ ]. Гиперграфы, являющиеся 1-простыми, принято также называть простыми или линейными. Для удобства и краткости изложения в дальнейшем тексте

пп "гиперребро" просто "ребро".

Определим понятия правильной раскраски и хроматического чис-

г

отображение / : V ^ {1,... ,г}. Ребро А Е Е гиперграфа Н = (V, Е)

называется одноцветным в раскраске /, если всем вершинам А присвоен один и тот же цвет в /. Правильной раскраской гиперграфа Н назовем

Н

Н

раскраска в г цветов, то говорят, что Н является г-раскрашиваемым.

Н

г Н г

графа Н будем обозначать через х(Н). Гиперграф обладает свойством B (в англоязычной литературе используется термин Property B), если х(Н) ^ 2. Справедливой раскраской называется правильная раскраска, при которой мощности всех цветовых классов отличаются не более чем на единицу (тем самым, все цвета задействуются почти одинаковое число раз). Последнее означает, что множество вершин V можно разбить не просто на r независимых множеств (т.е. подмножеств V, не содержащее целиком ни одного гиперребра гиперграфа Н), а на r независимых множеств почти одинакового размера.

Теория раскрасок графов и гиперграфов берет свое начало со знаменитой Проблемы о четырех красках, которая утверждает, что любой планарный граф является 4-раскрашиваемым. История попыток решения данной проблемы уходит в XIX век, полное же доказательство было получено только в 1977 году Аппелем и Хакеном [ ] с привлечением компьютерного перебора.

Еще одним историческим истоком теории раскрасок гиперграфов явились классические результаты теории Рамсея. Под теорией Рамсея обычно понимается набор фактов из разных разделов математики (анализа, теории чисел, геометрии, комбинаторики), объединенных общим принципом, что "при разбиении любой достаточно большой регулярной структуры на ограниченное число частей найдется часть, содержащая регулярную подструктуру меньшего размера". Считается [ ], что Рамсей стал заниматься подобными вопросами с целью доказать гипотезу Рассела-Уайтхеда [ ] о том, что все математические истины могут быть выведены из ограниченного набора аксиом. Так, Гильберт предполагал, что можно найти алгоритм, который бы позволял проверять, следует или

нет данное утверждение из некоторой заданной системы аксиом. Рамсей показал, что в частном случае такой алгоритм существует [ ]. Доказательство же отсутствия в общем случае было сделано Гёделем [ ], Тьюрингом [ ] и группой их последователей. Многие утверждения из теории Рамсея можно сформулировать в терминах раскрасок гиперграфов. Знаменитая теорема Рамсея [ ] утверждает, что для произвольных натуральных r, s найдется такое число R(s, t), что для любого n ^ R(s, t) в любой раскраске ребер полного графа нап вершинах в два цвета найдет-

s

t

торого будут покрашены во второй цвет. Задача о поиске значений чисел Рамсея R(s, t) легко может быть переформулирована в терминах раскрасок гиперграфов. Например, при s = t речь идет о 2-раскрашиваемости

n

s

Вопрос о возможности 2-раскрашиваемости однородных гиперграфов поднимается и в центральной проблеме теории раскрасок гиперграфов проблеме Эрдеша-Хайнала [ ]. В ней требуется найти величину ш(п),

n

свойством Б:

m(n) = min{|E| : H = (V, E) — п-граф, x(H) > 2}.

Поиску нижних оценок величины m(n) посвящены работы Алона, Спенсера, Ловаса, Сеймура, Бека, Косточки, Радхакришнана, Сринива-сана, Плухара, Шабанова, Козика, Черкашина и многих других.

Под задачами типа Эрдеша-Хайнада принято понимать разного рода обобщения задачи Эрдеша-Хайнада. Помимо естественного обобщения на случай гиперграфов с хроматическим числом больше г [ , ], задача Эрдеша-Хайнада ставится для множества других типов раскрасок. Перечислим некоторые из них:

• полноцветные раскраски (в этом случае, наоборот, требуется, чтобы каждое ребро содержало вершины всех цветов) [ , ];

•

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

•

при этом нужно избежать появления одноцветных ребер и минимизировать отношения количества всех цветов по отношению к числу цветов, в которое красится вершина) [ , ], связанные с задачами о многократном покрытии множества;

•

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

г

рое по мере увеличения размера ребра становится всё слабее) [ , ].

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

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

п-граф с х(Н) > 2, у которого |Е| < ^^т2п22п. Данную оценку пытались улучшить много лет, но пока никому не удалось. Некоторые исследователи выдвигали гипотезу, что данную оценку можно улучшить, если рассматривать неоднородные гиперграфы [ ]. Однако, на сегодняшний день пока таких результатов не известно. Дюрай, Козик и Шабанов [ ] недавно показали, что случайный п-граф с числом ребер |Е| < (1 — с)е42п22п почти наверное является 2-раскрашиваемым, т.е. имеет хроматическое число равное двум.

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

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

струмента, созданного изначально для задач о раскрасках гиперграфов, является знаменитая Локальная лемма, впервые сформулированная в 1973 году в работе Эрдеша и Ловаса [ ]. Суть этого утверждения состоит в том, что если некоторые события на вероятностном пространстве, с одной стороны, по-отдельности не слишком вероятны, а, с другой стороны, среди них "мало зависимостей", то с положительной вероятностью ни одно из них не произойдет. Локальная лемма также иногда давала ответ в некоторых задачах, где вероятность исследуемого события экспоненциально мала от размерности задачи. Поэтому это в дальнейшем породило серию исследований, связанных с поиском детерминированных и рандомизированных алгоритмов, решающих данные задачи за полиномиальное время. Так в 1991 году Бек [ ] предложил метод, позволяющий решать некоторые задачи Эрдеша с небольшими потерями в константах. А в 2010 году Мозер и Тардос предложили свой алгоритмический вариант Локальной Леммы Ловаса (FIX-IT алгоритм) [ ]. За этот очень яркий результат теоретической информатики они в 2020 были удостоены премии Геделя.

Перейдем к более детальному обсуждению задач диссертации. Первая задача диссертационного исследования это проблема типа Эрдеша Хайнала для класса b-простых гиперграфов. В 1973 году Эрдеш и Ловас

n

хроматическим числом. Ими же была поставлена задача о минималь-

n

r

обобщение проблемы для класса b-простых гиперграфов, введя величину m(n, r, b), равную минимально возможному числу ребер b-простого

п-графа с хроматическим числом больше г. Поиску асимптотических оценок величины ш(п,г,Ь) при различных соотношениях между параметрами посвящены работы Косточки и Кумбхата [ ], Бомана, Фриза и Мубаи [ ], Косточки и Рёдля [ ] и других. В диссертационной работе получена новая нижняя оценка величины ш(п,г,Ь)7 которая улучшает ранее известный результат из работы [ ].

В основе доказательства новой нижней оценки т(п,г,Ь) лежит результат, который можно назвать центральным в первой главе. Он дает

Ь

пг

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

п

их оценки были посвящены работы Радхакришнана и Сринивасана [ ], Черкашина и Козика [ ], Акользина и Шабанова [ ] и др. Ясно, что в

Ь

г

быть сильнее. И действительно, как показал Сабо в 1990 году [ ] данный подкласс гиперграфов "проще красить" и для него оценку можно заметно усилить. Кроме того, на основе этой техники можно раскрашивать гиперграфы, в некотором смысле близкие к простым, например, гиперграфы арифметических прогрессий, возникающие при оценке функции Ван дер Вардена. Результат Сабо был в дальнейшем обобщен и усилен в работах Косточки и Кумбхата [ ], Козика [ ], Купавского и Шабанова [ ], Козика и Шабанова [ ]. В диссертации получена новая оценка макси-

гЪ

п

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

А

ко правильную, но и справедливую раскраску в А + 1 цветов. Стоит отметить, что первоначальное доказательство Хайнала и Семереди было достаточно длинным. Уже в текущем столетии Киерстед и Косточка [ ] нашли короткое и простое доказательство. Кроме того, они уточнили [ ] этот результат для случая максимальной степени ребра и вместе с Мидларцем и Семереди [ ] построили быстрый алгоритм конструирования искомой справедливой раскраски. Справедливые раскраски гиперграфов изучались также интенсивно. Первый результат типа Хайнала Семереди, дающий наличие справедливой раскраски вершин гиперграфа в терминах ограничения на максимальную степень вершины, был неявно получен в работе Лу и Секеи [ ], где они получили некоторый общий результат об упаковках гиперграфов. В работе Шабанова [ ] данный результат был усилен для случая двух цветов. В диссертации рассматривается задача типа Эрдеша Хайнала для справедливых раскрасок, а

п

г

порядку с наилучшими оценками числа ребер из работ [ , ], которые

г

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

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

Цель работы.

Целью диссертации является изучение задач типа Эрдеши Хиинили о раскрасках гиперграфов для некоторых классов гиперграфов и раскрасок. Основными задачами диссертации являются:

• изучение количественной взаимосвязи между хроматическим числом и другими характеристиками (максимальной степенью ребра, числа ребер) ^простого п-графа;

• исследование возможности справедлив ой раскраски п-графа в заданное число цветов в терминах ограничения на число ребер.

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

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

1. Получено новое достаточное условие г-раскрашиваемости Ь-простого п-графа в терминах ограничения на максимальную степень ребра.

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

г

3. Получено новое достаточное условие справедливой 2-раскрашиваемости п

падает по порядку с наилучшей подобной оценкой Ридхикришнини Сринивасана для правильной 2-раскрашиваемости.

г

п-графа, г > 2, в виде ограничения на число ребер. Полученная оценка совпадает по порядку с наилучшей подобной оценкой Черкашина-

г

Теоретическая и практическая ценность.

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

Методология и методы исследования.

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

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

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

1. Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2017». (Москва, 2017).

2. First Russian-Hungarian Workshop on Discrete Mathematics, April 21 -April 23, Moscow, 2017. (Москва, 2017).

3. 18th International Conference on Random Structures and Algorithms. (Гнезно, Польша, 2017).

4. European Conference on Combinatorics, Graph Theory and Applications 2017. (Вена, Австрия, 2017).

5. Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2018». (Москва, 2018).

6. 2nd Russian-Hungarian Workshop, June 27-29, 2018. (Будапешт, Венгрия, 2018).

7. 61-ая Всероссийская научная конференция МФТИ. (Долгопрудный, 2018).

8. Научная конференция «Экстремальная комбинаторика и дискретная геометрия». (Майкоп, 2018).

9. 19th International Conference on Random Structures and Algorithms. (Цюрих, Швейцария, 2019).

Публикации.

Материалы диссертации опубликованы в 5 печатных работах [53-57], представленных в конце автореферата. Четыре работы в соавторстве. Данные работы опубликованы в журналах, индексируемых Scopus (все работы) и Web of Science (кроме [56]).

Личный вклад.

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

Структура работы.

Диссертация состоит из введения, трех глав, заключения и списка литературы. Общий объем диссертации 97 страниц. Библиография включает 57 наименований на 7 страницах.

Глава 1

Раскраски Ь-простых гиперграфов

Ь

перграфа с такими параметрами как максимальная степень ребра, максимальная степень вершины и количество ребер гиперграфа. Результаты опубликованы в работах [ ],[ ].

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

Связь хроматического числа и максимальной степени ребра А(Н) в гиперграфе Н впервые была рассмотрена в классической работе Эрдеша и Ловаса [ ], которые показали, что если

ал)

то х(Н) < г. Однако, как оказалось в дальнейшем, неравенство ( ) не является оптимальным и оценка максимальной степени ребра, обес-г

лена различными исследователями (см. обзор [ ] для более глубокого знакомства с этими результатами). Мы же отметим только последние

А(Н) < -гп-1,

сравнению с параметром однородности n, наилучший результат был получен Черкашиным и Козиком [ ]: если

r-1

Д(Н) < r rn-2, (1.2)

Vin n/

где c > 0 — некоторая абсолютная конетанта, то x(H) < r. Отметим, что в частном случае r = 2 данный результат был ранее доказан Радха-

r > n

оценка (1.2) становится хуже классической оценки (1.1). Данное недоразумение было исправлено в работе Акользина и Шабанова [ ], которые

r > n

n

Д(Н) < c--rn-1, (1.3)

in n

где c > 0 - некоторая константа, то H является r-раскрашиваемым.

Перейдем к обсуждению простых и b-простых гиперграфов. В своей

n

со сколь угодно большим хроматическим числом и поставили вопрос о нахождении количественной связи хроматического числа простого гиперграфа и его максимальной степени ребра. Первый нетривиальный результат здесь был получен в работе Сабо [ ], который показал, что для любого £ > 0 и любого простого n-графа H неравенство Д(Н) < n1-e2n означает 2-раскрашиваемость H, если n > n0(e). Данное утверждение было обобщено Косточкой и Кумбхатом в [ ]: для заданных b ^ 1, r ^ 2

и £ > 0 и п > по (г, Ь, г) любой б-простой п-граф Н с условием

А(Н) < п1-ег

1—1

(1.4)

г

• В случае г = 2 оценка ( ) заметно сильнее ( ), которая в данной ситуации принимает вид (п/ 1п п)1/22п, в то время как ( ) дает п1-о(1)2п.

• Величина £ > 0 в ( ) может быть выбрана сколь угодно малой при

п

функцию г(п), стремящуюся к нулю с ростом п.

Последнее наблюдение породило целую серию работ [ ], [ ], [ ] в которых авторы последовательно улучшали оценки на функцию г(п). Наконец, Козику и Шабанову [ ] удалось показать, что для случая простых гиперграфов можно положить г(п) = 0, а именно они установили, что Нп

где с > 0 - некоторая абсолютная константа, то Н является г- раскрашиваемым.

1.2 Основной результат первой главы

Ь

простых гиперграфов. Основной результат сформулирован в следующей теореме.

А(Н) < c • п гп—1,

(1.5)

Теорема 1. Пусть Ь ^ 1 — это натуральное число. Тогда существует такое щ(Ь), что для лю бого п ^ п0 (Ь) и любо го г ^ 2 всякий Ь-простой п-граф Н, удовлетворяющий условию

г

Сравним полученный результат с ранее известными. Ясно, что при Ь = 1 оценка () полностью совпадает с ( ). При Ь > 1 наилучшим оставался результат Козика из работы [ ], где была обоснована оценка

г

Ь > 1

п

графов, а не только Ь-простых, уже при г > 1п п.

Насколько результат теоремы 1 далек от максимально возможного? Как показали Косточка и Рёдль в [ ] для любых п,г ^ 2 существу-

пг степенью ребра не более п2гп-11п г. Тем самым, при фиксированных г

Ьп результата.

Д(Н) < (2в)-4пгп-ь,

(1.6)

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

Для доказательства теоремы 1 нам необходимо показать, что лю-Ьг раскрашиваемым. Основу доказательства составляет метод случайной перекраски, впервые предложенный Беком [ ]. Мы же используем его модификацию, примененную Козиком и Шабановым в [ ]. Опишем данный подход более детально.

Метод случайной перекраски

Пусть Н = (V, Е) — Ь-простой п-граф. Наша цель - построить неко-

г

зать, что она является правильной с положительной вероятностью. Для построения подобной раскраски зададим случайный порядок на множестве вершин гиперграфа V с помощью отображения а : V ^ [0,1], где а(^), V € V — независимые случайные величины с равномерным распределением на [0,1]. Значение а(V) будем называть весом вершины V. С вероятностью единица отображение а инъективно на V. Если а(V) < р, где р — некоторый параметр нашей конструкции, то вершину V будем называть свободной.

Рассмотрим также случайную раскраску вершин / : V ^ {0,... , г — 1}, имеющую равномерное распределение на множестве всех раскрасок. Предположим, что нам не повезло и в случайной раскраске f появились одноцветные ребра. Для исправления ситуации мы используем следующий алгоритм перекраски:

1. если в текущий раскраске имеется одноцветное ребро А цвета а €

{0,..., r — 1}, содержащее еще не перекрашивавшиеся свободные вершины, то выберем ту вершину v из них, которая имеет наименьший вес;

2. перекрасим вершину v в цвет (а + 1)(mod r);

3. будем говорить, что вершина v обвиняет ребро A;

4. повторяем первый шаг, пока возможно.

Формально, этот алгоритм может быть описан следующим способом:

Algorithm 1: Алгоритм перекраски 1 Input: f : V ^ {0,... , r — 1}, а : V ^ [0,1] инъекция ■2 while есть одноцветное ребро, в котором, первая

v

f(v) mod(r)

^ (f (v) + 1)

mod(r)

f

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

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

1.3.1 Конструкция Н-дерева

Пусть даже алгоритм не помог и по итогам его работы гиперграф

Н

почему ребро А оказалось одноцветным в финальной раскраске, нами будет далее построено специальное помеченное дерево, которое мы будем называть Н-деревом.

Но перед тем как приступить к описанию построения Н-дерева давайте сделаем несколько наблюдений касательно алгоритма перекраски. Если в процессе алгоритма перекраски некоторая вершина V перекрашивается, то она должна быть первой неперекрашенной свободной вершиной некоторого ребра которое в этот момент процедуры является одноцветным, то есть вершина V обвиняет ребро В случае если такое ребро ^ не одно, мы выбираем по одному для каждой вершины. Обратим внимание, что каждое одноцветное ребро может быть обвинено только одной вершиной.

Н

ем.

•А

здадим корневое дерево Т, состоящее из одного корневого узла помеченного ребром А. Во избежание путаницы вершины дерева Т будем называть узлами.

• Пусть а цвет одноцветного ребра А в финальной раскраске. Так как АА

а

вершины с изначальным цветом а — 1. Вершины последнего типа должны обвинять какие-то ребра, назовем эти ребра В1,... В данной ситуации мы также будем говорить, что ребро А обвиняет ребра В1,... , Б^. Добавим но вые £ узлов, помеченных В1,..., в дерево Т в качестве детей узла, помеченного ребром А.

• Поскольку каждое ребро Б^ должно было быть одноцветным цвета а — 1 на некотором этапе перекрашивания, то Б^ могло содержать

а — 1 а — 2

а—2

должны были обвинять некоторые другие ребра С1..., С\. Добавим новые узлов, помеченных С{... , С., в качестве детей узла, помеченного ребром Б{.

•

Т

Н

вило присвоения меток мы будем обозначать используя значок функции ф : V(Т) ^ Е(Н); мы также будем говорить, что узел и помечен ребром ф(и) или ф(и) - метка и.) Также обратим внимание что смежность в Т индуцируется отношением обвинения (Б является потомком А в Т, если и только если ребро ф(А) обвиняет ребро ф(Б)). При этом листья построенного Н-дерева помечены ребрами, одноцветными в изначальной

Т

Н

Следствие 1. Если, алгоритм перекраски не построил правильную рас-Н г Н

Доказательство данного факта следует из утверждения 4 работ [ ].

1.3.2 Локальная лемма

В [ ] Сабо исподьзововад специальный вариант Локальной Леммы, представляющий обобщение основного варианта, предложенного Беком [ ]. Мы же используем следующее обобщение из [ ].

Лемма 1. ( ) Пусть х = {Х1, Х2 ..., Хт} — независи-

мые случайные величины, (или, векторы,) на, произвольном, вероятностном, пространстве, а А = {А1,...,Ак} — множество событий, при-а

Для каждого А^ ^^^^^^^м через v6l(А^) минимальное подмножество случайных величин х таких, что А^ полностью принадлежит, порожденной ими а-алгебре. Далее, для, каждого X € х мы определяем многочлен шх(г):

Предположим, что существует многочлен ш(г), мажорирующий все многочлены шх(г), т.е. для любого действительного числа, г0 > 1 выполняется ш(г0) > шх(2о). Если существ уст т0 € (0,1)7 с условием, что

Тогда с положительной, вероятностью одновременно выполнены, все со-

шх (г) = ^ Р(А)^Ы(Л)|

(1.7)

ЛбА:Х €уЫ(Л)

(1.8)

бытия А, т.е.

р( р| А) > 0. (1.9)

Доказательство Локальной леммы можно посмотреть в [ ]. В нашей модели случайные независимые векторы — это пары величин (/(V), V € V, которые были присвоены каждой вершине V гиперграфа Н. Для каждой вершины V мы оценим вероятности всех плохих событий и далее будем суммировать их с соответствующими коэффициентами из (1.7). Для доказательства мы выберем следующие параметры:

1 51п п

т0 = ——г, Р = -

п + 1 п

Перейдем к анализу плохих событий.

1.3.3 Анализ плохих событий

Предположим, что алгоритм не помог и по итогам его работы гипер-НА

ТН

А

Плохое событие 1: много перекрашенных вершин

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

•С

а

(1.10)

• каждая вершина v £ С либо имела изначальный цвет f (v) = а, либо изначальный цвет — f (v) = а — 1 (mod r);

• число свободных вер шин в С (число к) хотя б ы 20e ln n;

• все вершины с изначальным цветом а — 1 являются свободными.

Обозначим через Bi(C) событие, описанное выше. Тогда вероятность события B1 (С) может быть оценена следующим образом:

p(Bi(C)) =r е (n)(1)n—''(?)k = r1—" e (k) (2p)k <

k>20e ln n 4 7 4 7 4 7 k>20e ln n 4 7

1—n v^ ^k = ri—n y- /10e ln n\ k <

< r1—n E T = r1—n E

k>20e ln n ^ 7 k>20e ln n

< r1—n e ^ \~l < r1—n21—20е ln n < 2 r1—'™n—Ю

k>20e ln n ^ 27

Следовательно, для каждой вершины V выполнена следующая оценка на полином из Локальной Леммы:

г^) = е p№(C»(^г

07 C: vGC 4 07

v

т.к. число ребер, инцидентных v, не превосходит Д(Н)) = Е Р(В1(С)^1 + Г) < 2Д(Н) • 2 r1—nn—10e <

C: vgc ^ n'

(используя условие (1.6)

2 1 1

< -— rn-6n • 2 r1-nn-10e = — r1-bn-9 < —--. (1.11)

" (2e)4 4e3 < 10(n + 1) v ;

Метку C, a также узел, помеченный этим ребром C, будем называть вырожденной меткой и вырожденным узлом, соответственно, если произошло событие B1(C). Далее, мы будем рассматривать h-деревья без вырожденных узлов.

Удаление повторяющихся ребер

Предположим, что T — это h-дерево с корнем, помеченным одноцветным в финальной раскраске ребром и в T нет вырожденных узлов. Для каждого узла C £ T введем понятие h-поддерева N(C), состоящего из всех узлов B h-дерева T, кратчайший путь из которых до корня C

h

нения. Так, если узел C - потомок узла F, тогда ребро ) содержит вершину v(0(C)), которая обвиняет ребро ), поэтому v(0(C)) £ 0(C) П ).

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

Утверждение 1. Пусть узлы, F1?...,Fs — потомки первого порядка, C

множеством ребер гиперграфа 0(F1),..., 0(Fs) w множеством перекрашенных вершин v(0(F1)),... , v(0(Fs)).

Доказательство. Ребро 0(C) было одноцветным некоторого цвета а на некотором шаге алгоритма перекраски. Поэтому есть вершинам £ 0(C),

которая была перекрашена в ф(С) последней (до того, как ребро ф(С) стало одноцветным цвета а). В свою очередь, вершина и должна была обвинить некоторое ребро ф(^), которое к моменту перекраски и должно было быть одноцветным цвета а — 1. Следователь но, | ф(С) П ф(^) | = 1 и и = ф(С) П ф(^) = v(ф(Fi)). Удалим теперь вершину и из ф(С) и повторим предыдущие рассуждения для оставшихся вершин. Таким образом мы установим взаимно однозначное соответствие между ..., ф(^)

и v(ф(Fl)),...,v(ф(Fs)). □

Предположим, что С и Б различные узлы в Т, но ф(С) = ф(Б). Такая ситуация происходит, когда обвиняющие вершины v(ф(C)) и v(ф(D)) совпадают. В дальнейшем, такие совпадающие узлы С и Б будем называть копиями. В случае простых гиперграфов такая ситуация может быть разрешена путем рассмотрения простых циклов в гиперграфе И. В случае Ь-простых гиперграфов такой подход не сработает, потому что

И

ствовать другим путем. Заметим, что если ф(С) = ф(Б), то (С)) и (Б)) тоже совпадают. Таким образом, свойство иметь копию наследуется. Исходя из этого, будем говорить, что вершина v специальная, если есть два различных узла С и Б в /г-дереве Т такие, что

• ф(С) = ф(Я);

• v = v(ф(C)) и v = v(ф(D));

• родите ли С и родители Б имеют различные метки.

/

ное.

Для заданного h-дерева (или h-иоддерева) Т, определим операцию удаления узлов с повторяющимися метками.

1. Зафиксируем некоторый порядок Z' на множестве ребер H. Будем нумеровать узлы h-дерева Т по возрастанию расстояния до корня, а если расстояния совпали для каких-то двух узлов, то нумеруем в соответствии с порядком Z' заданном на множестве их меток, если при этом номера Z' совпали (т.е. мы имеем случай совпадающих меток),

h

Обозначим через Z финальный порядок на множестве узлов Т.

2. Будем теперь рассматривать узлы в соответствии с порядком

3. Для текущего узла C, если имеется узел D с меткой 0(C) = 0(D)

C h C

всеми их потомками (т.е. удаляем D вместе с N (D), тел и D - копия C

4. Повторяем предыдущий шаг до тех пор пока возможно.

Обозначим через O(T) новое h-дерево, которое получилось после операции O. Ясно, что в O(T) нет двух узлов с совпадающими метками. Для h

рацию O мы можем сделать все h-деревья правильными. Поэтому всюду

h

Плохое событие 2: 6-непересекающиеся правильные h-деревья

Пусть теперь Т1 = O(T) — правильное h-дерево с корнем, помечен-

C

называть плохим узлом, если

Ф(С) п у ф(В) ^ Ь + 1,

ВбТДЖ (С)

т.е. ф(С) имеет не менее, чем Ь + 1 общую вершину с объединением ребер, которые являются метками узлов, не входящих в поддерево N (С).

/

поддереве.

Прямым путем в корневом дереве будем называть кратчайший путь, соединяющий узел с корнем. Возможно 2 случая:

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

2. В Т такого пути нет.

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

/ / Ь

/

/

Со

В плохом событии В2(Т) мы рассматриваем случай Ь-непересекающихся

т

Ф(С) П

(1.12)

г=3+1

правильных Н-деревьев Т. Пусть величина £ — это размер дерева Т, тогда выполнено следующее утверждение.

Утверждение 2. Число вершин гиперграфа Н по всем ребрам-меткам дерева Т не меньше, чем п + (п — Ь)(£ — 1).

Доказательство. Обозначим через (Ст,..., Со) путь, который содер-

Т

образом: сначала идут узлы Ст,... , С0, а потом все остальные узлы по возрастанию расстояния до корневого узла С0. Можно заметить, что каждый узел (кроме узлов Ст,..., С0) имеет номер меньше, чем любой его потомок и каждое ребро гиперграфа, являющееся меткой этого узла имеет не более Ь общих вершин со всеми ребрами-метками предыдущих узлов. Согласно свойству (1.12) это же выполняется для узлов Ст,..., С0. Ребро ф(Ст) содержит п вершин, а каждое из остальных

п — Ь

щие ребра. Учитывая, что размер Т равен получаем, что общее число вершин гиперграфа хотя бы п + (п — Ь)(£ — 1). □

Т

ф(С) содержит те больше, чем 10е 1п п вершин, которые были перекрашены до того, как ребро ф(С) стало одноцветным некоторого цвета а. Будем называть такой цвет а доминантным цветом ф(С) (для краткости цвет а будем также называть доминантным цветом узла С). Заметим, что в начальной раскраске / хотя бы п—10е 1п п вершин ребра ф(С) уже имеют доминантный цвет а. Конструкция Н-дерева обеспечивает важную вещь: если известен доминантный цвет корня Н-дерева Тх, то начальные цвета всех вершин гиперграфа, входящих в ф(Т), однозначно определяются по

Т1

/

/

Т

пал,и в ф(Т[) = ф(О(Т))7 однозначно определяются.

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

/ Т1

нумеруем оставшиеся узлы в соответствии с нумерацией ( и положим

^(Т[) = ^(ф(^\)),..., v(ф(Fs))}. Тогда для каждого следующего узла С

• нам известны все цвета всех общих вершин ф(С) с метками предков. Добавим их в

• нам известны все цвета в множестве П ф(С);

С

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

операции О, но в таком случае Тх содержит узел Е', являющийся копией Е. Метки родителей Е' содержат вершину и и номер родителей по ( меньше, чем номер С, поэтому и £ ^(Тх). □

Пусть ^(Тх) обозначает множество всех перекрашенных вершин в ф(Тх). Приведенное выше утверждение показывает, что это множество однозначно определяется по ребрам и их пересечениям. Более того, повторяя доказательство утверждения 1, мы получаем, что для каждого узла С вершина м(ф(С)) также однозначно определена.

Утверждение 4. Пусть А0 = А, Ах,..., х — это узлы в Тх. Тогда в каждом ф(А^) найдется подмножество вершин Я С ф(А^); такое что

1. \Щ\ ^ п — 20е 1пп — Ь для любого % = 1,..., £ — 1;

2. множества Я0,..., попарно не пересекаются, Я П Щ = 0, % =

3. все вершины в Я в изначальной рас краске / покрашены в доминантный цвет узла А^;

4- вершина м(ф(А^)) принадлежит Щ и это первая, вершина в Я (в соответствии с нумерацией а) для каждого % > 0.

Доказательство. Без потери общности предположим, что (Ат,..., А0) это прямой путь, который содержит все плохие узлы. Определим множество Щ для % = 0,..., ш, следующим образом:

т

Яг = Мф(Аг))} и ф(Аг) \ Я(Т0 и и ф(А,) . (1-13)

V j=г+1 /

Считаем, что ^(ф(А0))} равно пустому множеству. Для всех г > т, определим

щ = МФ(Л))} и ф(Аг) \ I ад) и и ^ I. (1.14)

\ ^(ГД^А)) )

Так как каждый узел Аг невырожденный, то |ф(Аг) П ^(Т1)| < 20е 1п п. Для г > т, Аг не плохой узел, поэтому |ф(Аг) П У^(А.)) ^| < Ь. Таким образом, |Щг| ^ п — 20е 1п п — Ь. Для г < т необходимое соотношение следует из ( ). Предположим, что узлы Ат+1,..., 1 занумерованы по возрастанию их расстояния до корня. Обозначим через Щ = Щ \ {v (Аг)}. При ] < г множество Щ может иметь непустое пересечение с ф(А_7) только тогда, когда А^- является родителем Аг. Но Щ не имеет пересечений с ближайшими потомками А^-, потому что обвиняющие вершины для их меток попадают в ^Т^). Множества Щ,..., Щт также не пересекаются, это следует из определения (1.13).

Если же г < т < ^ то Аг не может быть потомком А^-, отсюда Щ и Щ не могут пересекаться. Следовательно, в се множества Щ0,..., не пересекаются. Из определений (1.13) и (1.14) следует, что все эти множества не пересекаются с ^Т^), поэтому добавив вершины v(ф(Fi)) в непересекающиеся множества ^(Т1) мы по-прежнему будем иметь непересекающиеся множества Щ0,... , Поскольку Щ не пересекается с множеством меток ближайших потомков Аг, в начальной раекраске ] все вершины должны окрашены в доминантный цвет А. Более того, алгоритм говорит, что вершина v(ф(Ai)) может обвинить ф(Аг) тогда и только тогда, когда она является первой (с наименьшим весом) непере-крашенной вершиной в момент, когда ф(Аг) стало одноцветным. Итак,

м(ф(А^)) — это первая вершина в Я^.

□

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

Ь

вырожденных узлов Н-дерева Т размера £ вы,полнено

Доказательство. Согласно утверждению 3 вероятность того, что для данного зафиксированного доминантного цвета корня все вершины гиперграфа из ф(Тх) будут иметь заранее определенные цвета, равна г—т, где ш это число вершин в ф(Тх). Из утверждения следует, что ш ^ п + (п — Ь)(£ — 1).

Пусть А0 — это корень. Согласно утверждению для любого А^ £ Т1? А{ = А0, верши на м(ф(А^)) первая в множ естве Я^, размер которого хотя бы п — 20е 1п п — Ь. Все такие множества являются попарно непересекающимися, поэтому данные события независимы и вероятность может быть оценена следующим образом: (1/(п — 20е 1пп — Ь))*—1.

Наконец, все вершины из специального множества Я0 С А0 в изначальной раскраске / имеют доминантный цвет а и все они являются несвободными. Иначе алгоритм перекрасил бы одну из этих вершин, и ребро ф(А0) не могло бы стать одноцветным в финальной раскраске. Вероятность этого события равна (1 — < (1 — р)п—20е 1пДля завершения доказательства остается заметить, что Я0 не пересекается с

Р (В2(Т)) < r1_n_(n_b)(t_1)

п — 20е 1п п — Ь

1

) (1 — р)п—20е 1п п. (1.15)

остальными множествами

Все три события независимы и вместе составляют событие В2(Т). Значит, выполнена оценка (1.15). □

Утверждение 6. Пусть Н = (V, Е) — некоторый гиперграф с максимальной степенью ребра Д(Н) и пусть v £ V — произвольная вершина. Тогда, число к-деревьев Т размера Ь, содержащих вершину v во множестве вершин ф(Т) не превосходит (4Д(Н))*.

Доказательство. Воспользуемся следующей верхней оценкой числа корневых деревьев с непронумерованными вершинами: число непронумерованных деревьев размера Ь с заданным корнем не превосходит 4*/Ь. После того как выбрана структура (выбрано корневое дерево) есть Ь способов выбрать узел к-дерева, метка которого будет содержать фиксированную вершину ^ ^^^фграфа Н. После этого остается поставить в соответствие каждому узлу дерева ребро гиперграфа. Достаточно действовать по следующему правилу: для каждого еще неопределенного узла X, который смежен с уже определенным узлом Z, выбираем ребро, которое пересекается с Ясно, что ^ не больше чем (Д(Н) + 1) ребру

Д(Н)

способами, а выбор каждого следующего ребра возможен не более чем Д(Н) — 1

4*

Ь • (Д(Н) — 1)*_2 • Д(Н) • (Д(Н) + 1) • - < (4Д(Н))* (1.16)

Ь

Теперь все готово для того, чтобы получить нужную оценку на ло-

кадьыый полином для второго плохого события.

V

/ 1 \ /1 \ ип(в2№))|

^т^ = е гу <

0/ Т1: veф(Tl) 4 0/

^ |у1П(й2(т))|

iе I , г

< е е р(ад)) т + -) <

Т1: veф(Tl), ^М 4 /

(используя ( ) и оценку |у1п(В2 (т1))| < п£)

|е| ^ , \ ¿-1

е е ■

¿=1 Т1: veф(Tl), ^М

< У^ у^ г1-п-(п-6)(4-1П _1_ | х

< \ п — 20е 1п п — Ь I

х (1 - р)п-20е 1пп-У <

полагая п достаточно большим и используя утв. 6)

|Е 1 ( 2 \*-1

< ^(4Д(Я))'г1-п-(п-Ь)('-1) _ (Т - р)п-20е 1пп-У < ¿=1

|Е\ / л \ t / п \ Ь—1 / г 1 \ п—20е 1пп

< е (ж) ■■' (2) (■ - чг) <

'=1 ч(2е)4^ "10(п + 1)'

(1.17)

< п • П-5+0(1) У (-ДЛ = П-4+0(1) <

< 1=1 V (2е) /

Плохое событие 3: большое 6-непересекающиеся правильное Ь-поддерево

Сейчас мы предполагаем, что правильное Ь-дерево Т1 = 0(Т) не является 6-непересекающемся, но однако имеет Ь-поддерево Т", такое что Т{ = 0(Т') является ^непересекающемся правильным Ь-поддеревом размера хотя бы 1пп, ^ = 1Т1 ^ 1пп. Пусть Вз(Т{) — соответствующее событие. Ранее сформулированные утверждения 2 4 также применимы к

Список литературы диссертационного исследования кандидат наук Ахмеджанова Маргарита Булатовна, 2021 год

Литература

[1] Akolzin I., Shabanov D., Colorings of hypergraphs with large number of colors. Discrete Mathematics. - 2016. - Vol. 339, No.12. - P. 3020-3031.

[2] Appel K. Kenneth W., Solution of the Four Color Map Problem. Scientific American. - 1980. - Vol. 237, No. 4. - P. 108-121.

[3] Aslam J., Dhagat A., On-Line Algorithms for 2-Coloring Hypergraphs Via Chip Games. Theor. Comput. Sci. - Vol. 112, No. 2. - 1993. - P. 355-369.

[4] Beck J., On 3-chromatic hypergraphs. Discrete Math. - 1978. - Vol. 24. - P. 127-137.

[5] Berge C., Graphs and Hypergraphs. (Translated by E. Minicka). North-Holland Pub. Amsterdam. - 1973. - P. 542.

[6] Bernshteyn A., Kostochka A., DP-colorings of hypergraphs. European Journal of Combinatorics. - 2019,- Vol. 78. - P. 134-146.

[7] Bernshteyn A., The Johansson-Molloy theorem for DP-coloring. Random Structures and Algorithms. - 2019. - Vol. 54, No. 4. - P. 653-664.

[8] Bohman Т., Frieze A., Mubayi D., Coloring H-free hypergraphs. Random Structures and Algorithms. - 2010. - Vol.36, No.l. - P. 11-25.

[9] Liu C., An Upper Bound on the Fractional Chromatic Number of Triangle-Free Subcubic Graphs. SIAM Journal on Discrete Mathematics. - 2014. - Vol. 28, No. 3. - P. 110-1136.

[10] Cherkashin D. A note on panchromatic colorings. Discrete Mathematics. - 2018. - Vol. 341, No.3. - P. 652-657.

[11] Cherkashin D., Kozik J., A note on random greedy coloring of uniform hypergraphs. Random Structures and Algorithms. - 2015. - Vol. 47, No. 3. - P. 407-413.

[12] Duraj L., Gutowski G., Kozik J., A note on two-colorability of nonuniform hypergraphs. ICALP. - 2018. - No. 46. - P. 1-13.

[13] Dvorak Z., Ossona P., Wu H., 1-subdivisions, fractional chromatic number and Hall ratio. Comb. - 2020. Vol. 40, No. 6. - P. 759-774.

[14] Duraj L., Gutowski G., Kozik J., Chip games and paintability. Electronic journal of combinatorics. - Vol. 23, No. 3. - 2016. - 3.3.

[15] Duraj L., Kozik J., Shabanov D., Random hypergraphs and property B. Eur. J. Comb. - 2021. - Vol. 91. - 103205.

[16] Эрдёш П., Спенсер Дж., Вероятностные методы в комбинаторике. М. Мир. - 1976. - Р. 137.

[17] Erdos P., On a combinatorial problem. II. Acta Math. Acad. Sci. Hungar. - 1964. - V. 15, No. 3-4. - P. 445-447.

[18] Erdös P., Theory of Graphs and Its Applications (M. Fieldler, Ed.) Czech. Acad. Sei. Publ. Prague. - 1964. - Vol. 9. - P. 1-159.

[19] Erdös P., Loväsz. L., Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai. Amsterdam. North Holland. -1973. - Vol. 10. - P. 609-627.

[20] Erdös P., Hajnal A., On chromatic number of graphs and set systems. Acta Math. Acad. Sei. Hung. - 1966. - Vol. 17. - P. 61-99.

[21] Gebauer H., On the construction of 3-chromatic hypergraphs with few edges. Journal of Combinatorial Theory. Series A. - 2013. - Vol. 120, No.7 - P. 1483-1490.

[22] Gödel K., Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik. - 1931. - Vol. 38, No. 1. - P. 173-198.

[23] Hajnal A., Szemeredi E., Proof of a conjecture of P. Erdös. Combinatorial theory and its applications. North Holland. London. -1969. - Vol. 2. - P. 601-623.

[24] Kierstead H., Kostochka A., A short proof of Hajnal-Szemeredi Theorem on equitable coloring. Combin. Probab. Comput. - 2008.-Vol. 17, No. 2 - P. 265-270.

[25] Khor S., Application of graph colouring to biological networks. IET Syst. Biol. - 2010. - Vol. 4, No. 3. - P. 185-192.

[26] Khuzieva A, Shabanov D, Svyatokum P., On-line and list on-line colorings of graphs and hypergraphs. Moscow Journal of Combinatorics and Number Theory. -2017. - Vol. 7, No. 4. - P. 39-57.

[27] Kierstead H., Kostochka A., An Ore-type theorem on equitable coloring. J. Combin. Theory. Ser. B. - 2008. - Vol. 98, No. 1 - P. 226-234.

[28] Kierstead H., Kostochka A., Mydlarz M., Szemeredi M., A fast algorithm for equitable coloring. Combinatorica. - 2010. - Vol. 30, No. 2 - P. 217-224.

[29] Kostochka A., Mubayi D., Rodl V., Tetali P., On the chromatic number of set systems. Random Structures and Algorithms. - 2001.- Vol. 19, No. 2. - P. 87-98.

[30] Kostochka A., Rodl V., Constructions od sparse uniform hypergraphs with high chromatic number. Random Structures and Algorithms. -2010. - Vol. 36, No.l. - P. 46-56.

[31] Kostochka A., Coloring uniform hypegraphs with few colors. Random Structures and Algorithms. - 2010,- Vol. 24. - P. 1-10.

[32] Kostochka A., Kumbhat M., Coloring uniform hypergraphs with few edges. Random Structures and Algorithms. - 2009. - Vol. 35, No. 3 -P. 348-368.

[33] Kozik J., Shabanov D., Improved algorithms for colorings of simple hypergraphs and applications. Journal of Combinatorial Theory. Series B. - 2016. - Vol. 116, No.4. - P. 312-332.

[34] Kozik J., Improving Gebauer's Construction of 3-Chromatic Hypergraphs with Few Edges. Proceedings of the 48th International Colloquium on Automata, Languages, and Programming. - 2021.

[35] Kozik J., Multipass greedy coloring of simple uniform hypergraphs. Random Structures and Algorithms. - 2016. - Vol. 48, No. 1. - P. 125-146.

[36] Kupavskii A., Shabanov D., Colorings of uniform hypergraphs with large girth and applications. Doklady Akademii Nauk. - 2012. - Vol. 443, No. 4 - P. 422-426.

[37] Kupavskii A., Shabanov D., Colorings of Partial Steiner Systems and Their Applications. J Math Sci. - 2015. - Vol. 206 - P. 511-538.

[38] Leighton FT., A graph coloring algorithm for large scheduling problems. Journal of research of the National Bureau of Standards. - 1979. - Vol. 84, No. 6. - P. 1-489.

[39] Lotfi V., Sarin S., A graph coloring algorithm for large scale scheduling problems. Computers and Operations Research. - 1986. - Vol. 13, No. 1. - P. 27-32.

[40] Lu L., Szekely L., Using Lovasz Local Lemma in the space of random injections. Electron. J. Combin. - 2007. - Vol. 13. - P. 1-63.

[41] Moser R., Tardos G., A constructive proof of the general lovasz local lemma. Journal of the ACM. - 2010. - Vol. 57, No. 2. - P. 1-12.

[42] North A. N., Russell B. Principia Mathematica. Cambridge: Cambridge University Press. 2nd edition. - 1962. - P. 1-456.

[43] Radhakrishnan J., Srinivasan A., Improved bounds and algorithms for hypergraph two-coloring. Random Structures and Algorithms. - 2010.

- Vol. 16, No.l. - P. 4-32.

[44] Raigorodskii A., Shabanov D., The Erdos-Hajnal problem, its generalizations and related problems. Russian Mathematical Surveys.

- 2010. - Vol.66, No. 5. - P. 933-1002.

[45] Рии городски и A. M., Черкашин Д. Д., Экстремальные задачи в раскрасках гиперграфов. УМН. - 2020. - Vol. 75, No. 1:451. P. 95 154.

[46] Ramsey F., On a problem of formal logic. Proc. London Math. Soc. 2-nd ser. - 1930. - Vol. 30,- P. 264-286.

[47] Rozovskaya A, Shabanov D., Extremal problems for panchromatic colourings of uniform hypergraphs. Discrete Math. Appl. - 2012. - Vol. 22, No. 2. - P. 185-206.

[48] Shabanov D., Random coloring method in the combinatorial problem of Erdos and Lovasz. Random Structures and Algorithms - 2012. - Vol. 40, No. 2,- P. 227-253.

[49] Shabanov D.A. Equitable two-colorings of uniform hypergraphs. European Journal of Combinatorics. - 2015. - Vol. 43. - P. 185-203.

[50] Shangguan C., Tamo I., Sparse Hypergraphs with Applications to Coding Theory. SIAM J. Disc. Math. - Vol. 34, No. 3. - P. 1493-1504.

[51] Szabo Z., An application of Lovasz Local Lemma — a new lower bound for the van der Waerden number. Random Structures and Algorithms. _ 1990. - Vol. 1, No. 3. - P. 343-360.

[52] Turing A., Computing Machinery and Intelligence. Mind. - 1950. - Vol. 59, No. 236. - P. 433-460.

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

[53] Ахмеджанова М., О справедливых раскрасках гиперграфов. Ма-тем. заметки. - 2019,- Vol. 106, No.3. - P. 323-332.

[54] Akhmejanova M., Shabanov D., Colorings of b-simple hypergraphs. Electronic Notes in Discrete Mathematics. - 2017. - Vol. 61- P. 29-35.

[55] Akhmejanova M., Shabanov D., Equitable colorings of hypergraphs with few edges. Discrete Applied Mathematics. - 2020.- Vol. 276. -P. 2-12.

[56] Akhmejanova M., Shabanov D., Equitable colorings of hypergraphs with r colors. Fundamental and Applied Mathematics.- 2020. - Vol. 23, No.l. - P. 3-23.

[57] Akhmejanova M., Shabanov D., Coloring hypergraphs with bounded cardinalities of edge intersections. Discrete Mathematics.- 2020. - Vol. 343, No. 4. - 111692.