Содержание к диссертации
Введение
Глава 1 История и формулировки результатов 12
1.1 Основные определения и история задачи 12
1.2 Свойство В и его обобщения 13
1.3 Близкие задачи 17
1.4 Задачи с дополнительными ограничениями на класс гиперграфов 18
1.5 Задачи о раскрасках в несколько цветов 22
1.6 Задачи о подгиперграфах 23
1.6.1 Постановка задачи 23
1.6.2 Первый подход: є-свойство 24
1.6.3 Второй подход: -свойство 26
Глава 2 Доказательство нижней оценки mk(n) 28
2.1 Доказательство теоремы 2 28
2.1.1 Построение рандомизированного алгоритма раскраски . 28
2.1.2 Вероятностные основы алгоритма 29
2.1.3 Вспомогательные утверждения 31
2.1.4 Оценка вероятности события Ае 32
2.1.5 Оценка вероятности события Се 34
2.1.6 Оценка вероятности события BefjV 37
2.1.7 Оценка вероятности события Т 44
2.2 Доказательство теоремы 1 44
Глава 3 Доказательство верхней оценки т^(?г) 47
3.1 Доказательство теоремы 3 47
3.2 Доказательство леммы 3 49
Глава 4 Доказательство оценок rrik,h(n) 54
4.1 Доказательство теоремы 7 54
4.1.1 Предварительные замечания 54
4.1.2 Алгоритм раскраски вершин гиперграфа 55
4.1.3 Оценка вероятности события Ае 57
4.1.4 Оценка вероятности события Се 60
4.1.5 Оценка вероятности события Bef 67
4.1.6 Оценка вероятности события Т 70
4.2 Доказательство теоремы 6 70
4.3 Доказательство теоремы 4 73
4.4 Доказательство теоремы 5 73
Глава 5 Доказательства оценок р(п, 3) 75
5.1 Доказательство теоремы 8 75
5.2 Доказательство теоремы 10 78
5.3 Доказательство теоремы 9 82
Глава 6 є- и /-свойства 84
6.1 Доказательство теоремы 11 84
6.2 Доказательство теоремы 13 85
6.3 Доказательство теоремы 12 86
6.4 Доказательство теоремы 14 88
6.5 Задача о минимальном числе вершин 89
6.6 Доказательство теоремы 15 91
Список литературы 94
- Свойство В и его обобщения
- Построение рандомизированного алгоритма раскраски
- Предварительные замечания
- Доказательство теоремы 10
Введение к работе
Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике. Ранние результаты такого сорта основывались на сочетании комбинаторных соображений с элементарной вероятностной техникой, однако развитие метода в последние годы потребовало применения все более изощренных инструментов теории вероятностей. Еще одной причиной столь интенсивного развития вероятностного метода стало осознание важности роли, которую играет этот метод-в теории компьютерных вычислений, являющейся источником многих задач комбинаторики. В связи с этим, интересен также алгоритмический подход к изучению вероятностного метода в комбинаторике.
Одним из главных инициаторов применения вероятностного метода в дискретной математике выступил в 50-е годы XX века П. Эрдеш, который впоследствии внес в развитие метода очень значительный вклад. Его достижения, гипотезы и проблемы в существенной степени стимулировали исследования в этой области. Отныне результаты, получаемые вероятностным методом, можно разделить условно на две группы. К первой группе относятся те результаты, которые связаны с изучением определенных классов комбинаторных объектов, таких, как случайные графы или случайные матрицы (см. [13], [30], [31], [32], [33] и др.). Эти результаты являются по существу теоретико-вероятностными, хотя большинство из них мотивировано задачами комбинаторики. Вторая группа состоит из тех фактов, которые формулируются в терминах существования комбинаторных структур, обладающих рядом предписанных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью. Как правило, главная тонкость здесь в выборе подходящей вероятностной меры. Доказа-
тельства существования такого типа приводят к решениям различных эктре-мальных задач дискретной математики.
В диссертации получены результаты, которые в соответствии с изложенной выше условной классификацией можно отнести ко второй группе. В данном случае речь идет о применении вероятностного метода в различных задачах теории раскрасок гиперграфов. Напомним, что гиперграфом Н называется пара (V, Е), где V есть некоторое конечное множество (множество верішш гиперграфа), г, Е - это совокупность подмножеств множества V (множество ребер гиперграфа). В современной дискретной математике теория раскрасок графов и гиперграфов играет одну из центральных ролей. Эта теория имеет приложения в областях, на первый взгляд, имеющих мало общего с раскрасками. Вообще, задачи о раскрасках тесно связаны с фундаментальной проблемой разделения множества объектов на классы, удовлетворяющие определенным условиям.
В задачах теории раскрасок гиперграфов вероятностный метод был впервые применен П. Эрдешем (см. [1], [2]) для отыскания величины m(n,2), равной минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных1 двухцветных раскрасок. Дальнейшее развитие метод Эрдеша, в рамках которого вершинам гиперграфа цвета присваивались случайным образом, получил в работах Й. Бека (см. [3]) и Дж. Спенсера (см. [4]). Указанными авторами был предложен подход, основанный на построении рандомизированного алгоритма перекраски вершин гиперграфа, и этот подход идейно и технически гораздо сложнее метода Эрдеша. Позднее, Дж. Радхакришнан и А. Сринивазан (см. [5]) усовершенствовали алгоритм Бека - Спенсера и получили наилучший, на сегодняшний день, результат в задаче о величине т(п, 2).
Диссертация состоит из шести глав. В первой главе обсуждается история наиболее известных задач о нахождении минимального числа ребер гиперграфов, принадлежащих различным классам, даются необходимые определения, а также приводятся формулировки большинства полученных соискателем результатов. Во второй и третьей главах доказываются, соответственно, нижняя и верхняя оценки величины mk(n), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не допускающих такую двухцветную раскраску, в которой все ребра гиперграфа содержат не менее к вершин каждого цвета. Теорема о нижней оценке является центральным результатом работы. Доказательство этой теоремы основано на построении нового нетривиального рандомизированного алгоритма раскраски вершин гиперграфа. Четвертая глава посвящена доказательству результатов в
Раскраска (вершин) гиперграфа называется правильной, если в ней все ребра неодноцветны.
задачах с дополнительными ограничениями на пересечения ребер гиперграфов. Эти задачи близки к проблемам, связанным с теоремой Эрдеша - Ко -Радо (подробнее см. [18], [19], [20], [21]). В пятой главе изложены доказательства теорем об оценках экстремальных характеристик гиперграфов в случае раскрасок в три цвета. Шестая глава связана с различными задачами о под-гиперграфах.
Автор глубоко признателен научному руководителю А. М. Райгородскому за постановку задач, постоянное внимание и интерес к работе.
Общая характеристика работы
Актуальность темы диссертации
Настоящая работа посвящена изучению экстремальных характеристик, возникающих в задачах о раскрасках равномерных гиперграфов. В общем случае рассматриваемую проблему можно сформулировать так: найти минимальное число ребер гиперграфа, находящегося в классе п-равномерных гиперграфов, которые не допускают раскрасок определенного типа.
Подобные задачи впервые были рассмотрены в работах П. Эрдеша. Так, в 1960-х гг. Эрдешем была предложена (см. [1], [2]) следующая проблема: найти величину т(п,2), равную минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных двухцветных раскрасок, или, как ewte говорят, не обладают свойством В. Дальнейшее развитие данная проблема получила в работах таких замечательных специалистов в области вероятностной комбинаторики, как И. Бек, Дж. Спенсер, Дж. Радхакришанан и А. Сринивазан (см. [3], [4], [5]). Ими были разработаны так называемые рандомизированные алгоритмы раскрасок вершин гиперграфа, с помощью которых и были получены наилучшие известные оценки величины га(п, 2).
Задача о величине т(п, 2) имеет важные обобщения в случае г-цветных раскрасок. Первое обобщение связано с понятием хроматического числа гиперграфа. Через т(п, г) обозначим минимальное число ребер гиперграфа в классе п-равномерных гиперграфов, не допускающих правильных г-цветных раскрасок (т.е. имеющих хроматическое число, большее г). Изучению этой величины при различных соотношениях между параметрами п и г посвящены работы таких известных математиков, как Н. Алон и А. Косточка (см. [7], М).
Второе обобщение связано с рассмотрением радужных раскрасок. Различные экстремальные свойства равномерных гиперграфов, обладающих радужными2 r-раскрасками, изучались П. Эрдешем, Л. Ловасом, А. Косточкой, Д.
2Раскраска вершин гиперграфа в г цветов называется радужной r-раскраской, если в этой раскраске любое ребро содержит вершины всех г цветов.
Вудоллом и др. (см. [14], [34]). Обозначим через р(п,г) минимальное число ребер гиперграфа в классе n-равномерных гиперграфов, не допускающих радужных г-раскрасок. Ясно, что р(п, 2) = т(п, 2). В работах [14], [24] были получены общие оценки величины р(п, г). С помощью вероятностного метода в диссертации доказываются улучшенные оценки величины р(п, 3).
При изучении раскрасок равномерных гиперграфов особый интерес представляют задачи с дополнительными условиями на пересечения ребер гиперграфа. Например, хорошо известна задача (см. [14], [16], [17]) о величине т*(п,г), равной минимальному числу ребер гиперграфа в классе п-равномерных простых гиперграфов (т.е. таких гиперграфов, у которых любые два ребра имеют не более одной общей вершины), не допускающих правильных r-цветных раскрасок. В диссертации рассматриваются также задачи о раскрасках гиперграфов в случае, когда совокупности их ребер удовлетворяют некоторым условиям, которые тесно связаны с проблемами пересечений множеств и, в частности, с классической теоремой Эрдеша - Ко - Радо (см. [18], [19], [20], [21]).
Экстремальные задачи о раскрасках равномерных гиперграфов являются одними из наиболее сложных и, в то же время, одними из наиболее популярных в теории гиперграфов. Несмотря на то, что во многих из них не найдены точные ответы, полученные результаты имеют множество приложений в других областях, например, в теории алгоритмов. Интерес также представляют применяемые в диссертации вероятностные методы, отдельная разработка которых также является важной и, одновременно, сложной задачей.
Цель и задачи исследования
Целью диссертационной работы является получение различных результатов в экстремальных задачах о раскрасках равномерных гиперграфов. Основными задачами диссертации являются задачи разработки вероятностных алгоритмов раскрасок вершин гиперграфов для доказательства существования раскрасок определенного вида, а также задачи получения оценок минимального числа ребер гиперграфа в некоторых классах равномерных гиперграфов.
Научная новизна полученных результатов
Все результаты диссертации являются новыми.
Практическая значимость полученных результатов
Диссертация носит теоретический характер. Результаты и методы работы могут быть полезными при изучении вероятностного метода в комбинаторике, в исследованиях свойств равномерных гиперграфов, в экстремальных задачах теории гиперграфов, при практическом поиске некоторых раскрасок у равномерных гиперграфов.
Основные положения диссертации, выносимые на защиту
1. Для величины 7п^(п), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Bk (т.е. не допускающих двухцветных раскрасок, в которых любое ребро гиперграфа содержит не менее к вершин каждого цвета), при параметре к = к(п), удовлетворяющем условию к <С Inn, выполняется оценка
і е-| 2п~к
тк[п)»(йд
y/2k=T Ct1
(теорема 1).
2. Для величины mk{n) при условии к = о (j^) имеет место оценка
. . ,, че1п2 2 2п mk{n) < ip{n)—-—п
к-1
г=0
где фукция ф(п) -> 1 при п —У со (теорема 3).
3. Для величины га^й(п), равной минимальному количеству ребер гипер
графа в классе n-равномерных гиперграфов, обладающих свойством Ад
(ребра таких гиперграфов не имеют общих вершин, либо имеют не ме
нее h общих вершин), но не обладающих свойством !?&, при некоторых
ограничениях, наложенных на параметры к и /г, выполняются оценки
Ґ Зп \* 2п . , о 2n~h
(теоремы 5 и 6).
4. Для величины р(п, 3) имеют место оценки
з ,-4,. ,.ччп2е1пЗ /ЗЛ71
(^У<р(п,3)< (1 + 0(1))
(теоремы 8 и 9).
5. Для величины га&)Є(п), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Bk) (гиперграф обладает свойством Bk,E> если из него можно так удалить є долю ребер, чтобы оставшиеся ребра образовывали гиперграф, обладающий свойством Bfc), при условиях к — 1 <С |1п(сЛ)| < Inn — 3 In Inn выполнена оценка
An е~к 2п~2к гпк){п) >
ln(cA)|2fc-lgc.:
г'=0
где с - некоторая константа из интервала (0,1), а А = |г— (теорема 12).
i-0
б. Для величины fki(n), равной минимальному числу вершин гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Fkti (гиперграф обладает свойством Fkj, если из него можно так удалить I ребер, чтобы оставшиеся ребра образовывали гиперграф, обладающий свойством Bk), найдено точное значение (теорема 14).
Личный вклад соискателя
Все результаты диссертации получены соискателем самостоятельно.
Апробация результатов
Результаты диссертации докладывались на международной конференции "Дискретный анализ и исследование операций" (г. Новосибирск, 2004 г.), на международной конференции "Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложениям" в Праге (Чехия, 2006 г.), на международной конференции "Горизонты Комбинаторики" в Ба-латональмади (Венгрия, 2006 г.), на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О. Б. Лупанова (Москва, 2007 г.), на международной конференции "Европейская Комбинаторика" в Севилье (Испания, 2007 г.); на Ломоносовских чтениях в Московском Государственном Университете в 2004 г., а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на Большом семинаре кафедры теории вероятностей механико-математического факультета
МГУ под руководством чл.-корр. РАН А. Н. Ширяева, на семинаре д.ф.-м.н. А. М. Зубкова в МИРАН, на семинаре проф. С. В. Конягина в МГУ, на семинаре проф. Н. Г. Мощевитина в МГУ и др.
Опубликованность результатов
Результаты диссертации опубликованы в работах [35] - [43] списка литературы. Всего по теме диссертации опубликовано 9 работ.
Структура и объем диссертации
В диссертации имеется введение, общая характеристика работы, шесть глав, список литературы. Полный объем 97 страниц, из них 4 страницы занимает список литературы (43 наименования).
Свойство В и его обобщения
Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике. Ранние результаты такого сорта основывались на сочетании комбинаторных соображений с элементарной вероятностной техникой, однако развитие метода в последние годы потребовало применения все более изощренных инструментов теории вероятностей. Еще одной причиной столь интенсивного развития вероятностного метода стало осознание важности роли, которую играет этот метод-в теории компьютерных вычислений, являющейся источником многих задач комбинаторики. В связи с этим, интересен также алгоритмический подход к изучению вероятностного метода в комбинаторике.
Одним из главных инициаторов применения вероятностного метода в дискретной математике выступил в 50-е годы XX века П. Эрдеш, который впоследствии внес в развитие метода очень значительный вклад. Его достижения, гипотезы и проблемы в существенной степени стимулировали исследования в этой области. Отныне результаты, получаемые вероятностным методом, можно разделить условно на две группы. К первой группе относятся те результаты, которые связаны с изучением определенных классов комбинаторных объектов, таких, как случайные графы или случайные матрицы (см. [13], [30], [31], [32], [33] и др.). Эти результаты являются по существу теоретико-вероятностными, хотя большинство из них мотивировано задачами комбинаторики. Вторая группа состоит из тех фактов, которые формулируются в терминах существования комбинаторных структур, обладающих рядом предписанных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью. Как правило, главная тонкость здесь в выборе подходящей вероятностной меры. Доказа тельства существования такого типа приводят к решениям различных эктре-мальных задач дискретной математики.
В диссертации получены результаты, которые в соответствии с изложенной выше условной классификацией можно отнести ко второй группе. В данном случае речь идет о применении вероятностного метода в различных задачах теории раскрасок гиперграфов. Напомним, что гиперграфом Н называется пара (V, Е), где V есть некоторое конечное множество (множество верішш гиперграфа), г, Е - это совокупность подмножеств множества V (множество ребер гиперграфа). В современной дискретной математике теория раскрасок графов и гиперграфов играет одну из центральных ролей. Эта теория имеет приложения в областях, на первый взгляд, имеющих мало общего с раскрасками. Вообще, задачи о раскрасках тесно связаны с фундаментальной проблемой разделения множества объектов на классы, удовлетворяющие определенным условиям.
В задачах теории раскрасок гиперграфов вероятностный метод был впервые применен П. Эрдешем (см. [1], [2]) для отыскания величины m(n,2), равной минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных1 двухцветных раскрасок. Дальнейшее развитие метод Эрдеша, в рамках которого вершинам гиперграфа цвета присваивались случайным образом, получил в работах Й. Бека (см. [3]) и Дж. Спенсера (см. [4]). Указанными авторами был предложен подход, основанный на построении рандомизированного алгоритма перекраски вершин гиперграфа, и этот подход идейно и технически гораздо сложнее метода Эрдеша. Позднее, Дж. Радхакришнан и А. Сринивазан (см. [5]) усовершенствовали алгоритм Бека - Спенсера и получили наилучший, на сегодняшний день, результат в задаче о величине т(п, 2).
Построение рандомизированного алгоритма раскраски
Доказательство этой теоремы основано на построении нового нетривиального рандомизированного алгоритма раскраски вершин гиперграфа. Четвертая глава посвящена доказательству результатов в Раскраска (вершин) гиперграфа называется правильной, если в ней все ребра неодноцветны. задачах с дополнительными ограничениями на пересечения ребер гиперграфов. Эти задачи близки к проблемам, связанным с теоремой Эрдеша - Ко -Радо (подробнее см. [18], [19], [20], [21]). В пятой главе изложены доказательства теорем об оценках экстремальных характеристик гиперграфов в случае раскрасок в три цвета. Шестая глава связана с различными задачами о под-гиперграфах.
Автор глубоко признателен научному руководителю А. М. Райгородскому за постановку задач, постоянное внимание и интерес к работе. Общая характеристика работы Актуальность темы диссертации Настоящая работа посвящена изучению экстремальных характеристик, возникающих в задачах о раскрасках равномерных гиперграфов. В общем случае рассматриваемую проблему можно сформулировать так: найти минимальное число ребер гиперграфа, находящегося в классе п-равномерных гиперграфов, которые не допускают раскрасок определенного типа.
Подобные задачи впервые были рассмотрены в работах П. Эрдеша. Так, в 1960-х гг. Эрдешем была предложена (см. [1], [2]) следующая проблема: найти величину т(п,2), равную минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных двухцветных раскрасок, или, как ewte говорят, не обладают свойством В. Дальнейшее развитие данная проблема получила в работах таких замечательных специалистов в области вероятностной комбинаторики, как И. Бек, Дж. Спенсер, Дж. Радхакришанан и А. Сринивазан (см. [3], [4], [5]). Ими были разработаны так называемые рандомизированные алгоритмы раскрасок вершин гиперграфа, с помощью которых и были получены наилучшие известные оценки величины га(п, 2).
Задача о величине т(п, 2) имеет важные обобщения в случае г-цветных раскрасок. Первое обобщение связано с понятием хроматического числа гиперграфа. Через т(п, г) обозначим минимальное число ребер гиперграфа в классе п-равномерных гиперграфов, не допускающих правильных г-цветных раскрасок (т.е. имеющих хроматическое число, большее г). Изучению этой величины при различных соотношениях между параметрами п и г посвящены работы таких известных математиков, как Н. Алон и А. Косточка (см. [7], М).
Второе обобщение связано с рассмотрением радужных раскрасок. Различные экстремальные свойства равномерных гиперграфов, обладающих радужными2 r-раскрасками, изучались П. Эрдешем, Л. Ловасом, А. Косточкой, Д. Вудоллом и др. (см. [14], [34]). Обозначим через р(п,г) минимальное число ребер гиперграфа в классе n-равномерных гиперграфов, не допускающих радужных г-раскрасок. Ясно, что р(п, 2) = т(п, 2). В работах [14], [24] были получены общие оценки величины р(п, г). С помощью вероятностного метода в диссертации доказываются улучшенные оценки величины р(п, 3).
При изучении раскрасок равномерных гиперграфов особый интерес представляют задачи с дополнительными условиями на пересечения ребер гиперграфа. Например, хорошо известна задача (см. [14], [16], [17]) о величине т (п,г), равной минимальному числу ребер гиперграфа в классе п-равномерных простых гиперграфов (т.е. таких гиперграфов, у которых любые два ребра имеют не более одной общей вершины), не допускающих правильных r-цветных раскрасок. В диссертации рассматриваются также задачи о раскрасках гиперграфов в случае, когда совокупности их ребер удовлетворяют некоторым условиям, которые тесно связаны с проблемами пересечений множеств и, в частности, с классической теоремой Эрдеша - Ко - Радо (см. [18], [19], [20], [21]).
Экстремальные задачи о раскрасках равномерных гиперграфов являются одними из наиболее сложных и, в то же время, одними из наиболее популярных в теории гиперграфов. Несмотря на то, что во многих из них не найдены точные ответы, полученные результаты имеют множество приложений в других областях, например, в теории алгоритмов. Интерес также представляют применяемые в диссертации вероятностные методы, отдельная разработка которых также является важной и, одновременно, сложной задачей.
Предварительные замечания
Гиперграф обладает свойством Bk, если существует такая двухцветная раскраска множества его вершин, в которой любое ребро гиперграфа содержит не менее к вершин каждого цвета. Отметим, что из приведенного определения вытекает эквивалентность свойств В и В\. Ясно также, что если гиперграф обладает свойством В к, то он обладает и любым свойством В{ при г к. Введем еще несколько понятий, которые будут активно использоваться в дальнейшем. Определение 5. Пусть 9 - произвольная двухцветная раскраска вершин гиперграфа. Назовем ребро е плохим в 9, если в этой раскраске в ребре е число вершин одного из цветов меньше, чем к. При этом другой цвет назовем доминирующим в ребре е относительно 9. Остальные ребра, не являющиеся плохими в 9, назовем хорошими в 9. В терминах определения 5 критерий отсутствия свойства Вк у гиперграфа можно сформулировать следующим образом: гиперграф не обладает свойством Вк, если в любой двухцветной раскраске множества вершин гиперграфа есть плохое ребро. По аналогии с т(п,г) введем величину тк(п), как минимальное число ребер в некотором классе гиперграфов: гпк(п) = тт{\Е(Н)\: Н - n-равномерный гиперграф, не обладающий свойством Bk}. Из определения свойства Вк следует, что выполняется цепочка неравенств т(п, 2) = mi(n) 7i2(n) тз(п) Понятно также, что п-равномерный гиперграф может обладать свойством Вк только при условии к . В дальнейшем мы будем считать, что параметр к удовлетворяет этому условию и является функцией от п (к = к(п)), которая может расти с ростом п. Оцениванию величины тк(п) при различных значениях функции к и посвящены основные результаты данной работы.
В задаче о минимальном числе ребер гиперграфа, принадлежащего определенному классу, можно наложить дополнительные ограничения на этот класс помимо равномерности его элементов и значения их хроматического числа, которые имели место прежде (см. задачу об отыскании величины т(п, г)). Одним из классических подобных ограничений является требование простоты гиперграфа.
Отметим, что свойство Ah глубоко мотивировано задачами экстремальной комбинаторики, связанными с теоремой Эрдеша - Ко - Радо (подробнее см., например, [18], [19], [20], [21], [22]). Из определения 7 следует, что свойство А\ тривиально, им обладает любой гиперграф. В классической задаче о величине т(п, г) вводить дополнительное требование в виде свойства Ah при h 1 не имеет смысла. Для доказательства используем (рандомизированный) алгоритм построения искомой раскраски множества V. Он состоит из двух шагов.
На первом шаге покрасим вершины гиперграфа согласно схеме Бернулли: с вероятностью независимо присваиваем каждой вершине синий или красный цвет. Назовем получившуюся случайную раскраску первой раскраской.
После получения первой раскраски выделим "опасные" вершины. А именно, вершину v назовем "опасной", если существует ребро /, содержащее г/, являющееся плохим в первой раскраске, и при этом v имеет доминирующий цвет ребра /. Множество опасных вершин обозначим через D.
На втором этапе мы случайным образом "подправим" первую раскраску путем частичного перекрашивания опасных вершин. Для этого сначала случайно занумеруем вершины гиперграфа. Вероятность каждой нумерации равна тщ. Допустим, г і,г 2, - опасные вершины, записанные согласно полученной случайной нумерации, т.е. D = {у\,У2,...}. Рассмотрим их последовательно одну за другой. Пусть некоторые операции перекрашивания были совершены по отношению к вершинам г і,..., г г-_і и рассматривается опасная вершина Vi, имеющая в первой раскраске цвет А. Тогда существует некоторый набор ребер /і, /г,..., содержащих вершину V{ и плохих в первой раскраске, причем доминирующим цветом у этих ребер является цвет А. В каждом ребре fj множество вершин, покрашенных в цвет А на первом этапе алгоритма, обозначим через V3. Ясно, что \Vj\ п — к. Все вершины из Vj являются опасными, поэтому до рассмотрения vi часть из них могла поменять цвет. Если в хотя бы одном из множеств Vj число вершин, не поменявших цвет на момент рассмотрения Vi, по-прежнему больше n — к, то вершина г г- называется "по-прежнему опасной" и мы пытаемся ее перекрасить: с вероятностью р меняем ее цвет, а с вероятностью 1 — р не меняем. Если же вершина vi не является "по-прежнему опасной", то пропускаем эту вершину и переходим к Vi+i. Результат такого последовательного перекрашивания назовем второй раскраской.
Доказательство теоремы 10
Скажем, что алгоритм не привел к успеху, если во второй раскраске есть плохие ребра. Обозначим такое событие через Т. Покажем, что при п max(ni,iVi) вероятность Т меньше единицы и что, стало быть, существует раскраска, в которой у Я нет плохих ребер, то есть Я обладает свойством В . Из этого будет следовать утверждение теоремы. Ребро е может быть плохим в двух случаях. Либо е было плохим уже в первой раскраске и осталось плохим в процессе перекраски. Либо е не было плохим в первой раскраске, но стало таковым во второй. Через Ае обозначим такое событие: ребро е имело доминирующий красный цвет в первой раскраске и осталось плохим ребром с красным доминирующим цветом (или просто красным). Через Се обозначим другое событие: е имеет доминирующий красный цвет во второй раскраске, а в первой раскраске оно либо было хорошим, либо имело доминирующий синий цвет.
Поясним смысл параметров. В первой раскраске в ребре / число красных вершин должно быть меньше к, за это отвечает параметр j. Число красных вершин в f{ обозначим за аг- для г = 1, 2,3. Оставшиеся j — а\ — ач — а з красных вершин находятся в /4. Заметим, однако, что число красных вершин в /з не может быть меньше, чем у — к + 1. В самом деле, ни одна из тех вершин в /з, которые оказались синими в первой раскраске, не поменяла цвет в процессе перекраски. Значит, чтобы е могло быть красным во второй раскраске, этих вершин должно быть меньше к.
Далее, часть красных вершин в f\ могла изменить цвет в процессе перекраски, число подобных вершин обозначим через с\. Условие 4 в определении события Bef v говорит о том, что все синие вершины /і и /2 подвергались случайной перекраске. В /і перекрасилось Ъ\ синих вершин, но это число не пер-восходит k—1—j, иначе на момент рассмотрения v перекраска в / удалась бы. Среди красных вершин части /2 перекрасилось С2, причем сч к — 1 — у -\- а } иначе е во второй раскраске не сможет быть красным.
Следующий параметр 6г - число перекрасившихся синих вершин в /г -имеет более нетривиальные ограничения на область возможных значений. Поскольку перекраска в / до рассмотрения v не удалась, то &2 к — 1 — j — Ь\. С другой стороны, количество синих вершин в пересечении ребер после перекраски v должно быть меньше к, ведь v - последняя синяя вершина, поменявшая цвет, а е - красное во второй раскраске. Посчитаем число синих вершин в е П / после перекраски v. Несложно понять, что оно равно z — a i — Ъг + С2 + у — аз. Отсюда, учитывая, что z + у = h — 1, получаем нижнее ограничение на возможное значение Ьч: 62 h — к — ( — аз + сі Следующий за суммой по Ьч множитель р отвечает вероятности перекраски вершины v. Среди красных вершин части /з перекрасилось сз, следовательно, они добавились к уже имеющимся h — 1 — а — &2 + c i — аз синим вершинам в пересечении ребер. Число синих вершин в пересечении, как и во всем ребре е, должно быть меньше к во второй раскраске. Во-многом структура доказательства будет напоминать структуру доказательства теоремы 2. Однако возникнет и ряд значительных отличий (как идейных, так и технических). Доказательство разобьется на несколько частей, которые также хорошо нам знакомы. А именно, в первой части будет описан рандомизированный алгоритм построения искомой раскраски (т.е. раскраски, гарантирующей выполнение свойства Вь) и определены основные термины - в частности, события Се и Ае; во второй части будет приведена и обоснована оценка сверху вероятности события Ле; в третьей части будет дано определение события Bef и приведена оценка вероятности события Се; в четвертой то же самое будет сделано для вероятности события Bef, окончательные выводы и некоторые замечания составят заключительную пятую часть. Мы сразу сформулируем лемму, которая имеет технический характер и понадобится при оценке различных вероятностей.
