Вероятностные методы решения экстремальных задач о раскрасках равномерных гиперграфов тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Шабанов, Дмитрий Александрович

• Шабанов, Дмитрий Александрович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Шабанов, Дмитрий Александрович

Введение

Общая характеристика работы

Глава 1 История и формулировки результатов

§1.1 Основные определения и история задачи

§1.2 Свойство В и его обобщения.

§1.3 Близкие задачи.

§1.4 Задачи с дополнительными ограничениями на класс гиперграфов

§1.5 Задачи о раскрасках в несколько цветов.

§1.6 Задачи о подгиперграфах.

1.6.1 Постановка задачи.

1.6.2 Первый подход: е-свойство

1.6.3 Второй подход: ¿-свойство.

Глава 2 Доказательство нижней оценки тк(п)

§2.1 Доказательство теоремы 2.

2.1.1 Построение рандомизированного алгоритма раскраски

2.1.2 Вероятностные основы алгоритма

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

2.1.4 Оценка вероятности события Ае.

2.1.5 Оценка вероятности события Се

2.1.6 Оценка вероятности события

2.1.7 Оценка вероятности события Т.

§2.2 Доказательство теоремы 1.

Глава 3 Доказательство верхней оценки т^п)

§3.1 Доказательство теоремы 3.

§3.2 Доказательство леммы 3.

Глава 4 Доказательство оценок тк,н{п)

§4.1 Доказательство теоремы 7.

4.1.1 Предварительные замечания.

4.1.2 Алгоритм раскраски вершин гиперграфа.

4.1.3 Оценка вероятности события Ае.

4.1.4 Оценка вероятности события Се

4.1.5 Оценка вероятности события В^.

4.1.6 Оценка вероятности события Т.

§4.2 Доказательство теоремы 6.

§4.3 Доказательство теоремы 4.

§4.4 Доказательство теоремы 5.

Глава 5 Доказательства оценок р(п, 3)

§5.1 Доказательство теоремы 8.

§5.2 Доказательство теоремы 10.

§5.3 Доказательство теоремы 9.

Глава б £- и ¿-свойства

§6.1 Доказательство теоремы 11.

§6.2 Доказательство теоремы 13.

§6.3 Доказательство теоремы 12.

§6.4 Доказательство теоремы 14.

§6.5 Задача о минимальном числе вершин.

§6.6 Доказательство теоремы 15.

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

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

Одним из главных инициаторов применения вероятностного метода в дискретной математике выступил в 50-е годы XX века П. Эрдеш, который впоследствии внес в развитие метода очень значительный вклад. Его достижения, гипотезы и проблемы в существенной степени стимулировали исследования в этой области. Отныне результаты, получаемые вероятностным методом, можно разделить условно на две группы. К первой группе относятся те результаты, которые связаны с изучением определенных классов комбинаторных объектов, таких, как случайные графы или случайные матрицы (см. [13], [30], [31], [32], [33] и др.). Эти результаты являются по существу теоретико-вероятностными, хотя большинство из них мотивировано задачами комбинаторики. Вторая группа состоит из тех фактов, которые формулируются в терминах существования комбинаторных структур, обладающих рядом предписанных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью. Как правило, главная тонкость здесь в выборе подходящей вероятностной меры. Доказательства существования такого типа приводят к решениям различных экстремальных задач дискретной математики.

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

В задачах теории раскрасок гиперграфов вероятностный метод был впервые применен П. Эрдешем (см. [1], [2]) для отыскания величины т(п, 2), равной минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных1 двухцветных раскрасок. Дальнейшее развитие метод Эрдеша, в рамках которого вершинам гиперграфа цвета присваивались случайным образом, получил в работах Й. Бека (см. [3]) и Дж. Спенсера (см. [4]). Указанными авторами был предложен подход, основанный на построении рандомизированного алгоритма перекраски вершин гиперграфа, и этот подход идейно и технически гораздо сложнее метода Эрдеша. Позднее, Дж. Радхакришнан и А. Сринивазан (см. [5]) усовершенствовали алгоритм Бека - Спенсера и получили наилучший, на сегодняшний день, результат в задаче о величине т(п, 2).

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

1 Раскраска (вершин) гиперграфа называется правильной, если в ней все ребра неодноцветны. задачах с дополнительными ограничениями на пересечения ребер гиперграфов. Эти задачи близки к проблемам, связанным с теоремой Эрдеша - Ко -Радо (подробнее см. [18], [19], [20], [21]). В пятой главе изложены доказательства теорем об оценках экстремальных характеристик гиперграфов в случае раскрасок в три цвета. Шестая глава связана с различными задачами о под-гиперграфах.

Автор глубоко признателен научному руководителю А. М. Райгородскому за постановку задач, постоянное внимание и интерес к работе.

Общая характеристика работы

Актуальность темы диссертации

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

Подобные задачи впервые были рассмотрены в работах П. Эрдеша. Так, в 1960-х гг. Эрдешем была предложена (см. [1], [2]) следующая проблема: найти величину т(п, 2), равную минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных двухцветных раскрасок, или, как еще говорят, не обладают свойством В. Дальнейшее развитие данная проблема получила в работах таких замечательных специалистов в области вероятностной комбинаторики, как Й. Бек, Дж. Спенсер, Дж. Радхакришанан и А. Сринивазан (см. [3], [4], [5]). Ими были разработаны так называемые рандомизированные алгоритмы раскрасок вершин гиперграфа, с помощью которых и были получены наилучшие известные оценки величины т(п, 2).

Задача о величине т(п, 2) имеет важные обобщения в случае г-цветных раскрасок. Первое обобщение связано с понятием хроматического числа гиперграфа. Через т(п, г) обозначим минимальное число ребер гиперграфа в классе п-равномерных гиперграфов, не допускающих правильных г-цветных раскрасок (т.е. имеющих хроматическое число, большее г). Изучению этой величины при различных соотношениях между параметрами п и г посвящены работы таких известных математиков, как Н. Алон и А. Косточка (см.

7], й).

Второе обобщение связано с рассмотрением радужных раскрасок. Различные экстремальные свойства равномерных гиперграфов, обладающих радужными2 г-раскрасками, изучались П. Эрдешем, Л. Ловасом, А. Косточкой, Д.

2Раскраска вершин гиперграфа в г цветов называется радужной г-раскраской, если в этой раскраске любое ребро содержит вершины всех г цветов.

Вудоллом и др. (см. [14], [34]). Обозначим через р(п,г) минимальное число ребер гиперграфа в классе п-равномерных гиперграфов, не допускающих радужных г-раскрасок. Ясно, что р(п, 2) = т(п, 2). В работах [14], [24] были получены общие оценки величины р(п, г). С помощью вероятностного метода в диссертации доказываются улучшенные оценки величины р(п, 3).

При изучении раскрасок равномерных гиперграфов особый интерес представляют задачи с дополнительными условиями на пересечения ребер гиперграфа. Например, хорошо известна задача (см. [14], [16], [17]) о величине т*(п,г), равной минимальному числу ребер гиперграфа в классе п-равномерных простых гиперграфов (т.е. таких гиперграфов, у которых любые два ребра имеют не более одной общей вершины), не допускающих правильных г-цветных раскрасок. В диссертации рассматриваются также задачи о раскрасках гиперграфов в случае, когда совокупности их ребер удовлетворяют некоторым условиям, которые тесно связаны с проблемами пересечений множеств и, в частности, с классической теоремой Эрдеша - Ко - Радо (см. [18], [19], [20], [21]).

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

Цель и задачи исследования

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

Научная новизна полученных результатов

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

Практическая значимость полученных результатов

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

Основные положения диссертации, выносимые на защиту

1. Для величины т&(п), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Bk (т.е. не допускающих двухцветных раскрасок, в которых любое ребро гиперграфа содержит не менее к вершин каждого цвета), при параметре к = к(п), удовлетворяющем условию к <С Inn, выполняется оценка где фукция ф(п) —> 1 при п —ь оо (теорема 3).

3. Для величины т^л(п), равной минимальному количеству ребер гиперграфа в классе п-равномерных гиперграфов, обладающих свойством А^ (ребра таких гиперграфов не имеют общих вершин, либо имеют не менее К общих вершин), но не обладающих свойством В^ при некоторых ограничениях, наложенных на параметры к и к, выполняются оценки теорема 1).

2. Для величины т^{п) при условии к = о имеет место оценка к-1 ' Е С* к-1 теоремы 5 и 6). 4. Для величины р(п, 3) имеют место оценки п п2е In 3 12 п теоремы 8 и 9).

5. Для величины гпк,£(п), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Вк,£ (гиперграф обладает свойством Bk}£, если из него можно так удалить г долю ребер, чтобы оставшиеся ребра образовывали гиперграф, обладающий свойством В к), при условиях к — 1 <С |1п(сА)| < Inn — 3 In Inn выполнена оценка

An е~к 2п~2к т*(»> » гаж^т^' i=О где с - некоторая константа из интервала (0,1), а А = fr—- (теорема 12). с; г=0

6. Для величины /¿¿(п), равной минимальному числу вершин гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Fkj (гиперграф обладает свойством Fkj, если из него можно так удалить I ребер, чтобы оставшиеся ребра образовывали гиперграф, обладающий свойством Bk), найдено точное значение (теорема 14).

Личный вклад соискателя

Все результаты диссертации получены соискателем самостоятельно.

Апробация результатов

Результаты диссертации докладывались на международной конференции "Дискретный анализ и исследование операций" (г. Новосибирск, 2004 г.), на международной конференции "Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложениям" в Праге (Чехия, 2006 г.), на международной конференции "Горизонты Комбинаторики" в Ба-латональмади (Венгрия, 2006 г.), на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О. Б. Лупанова (Москва, 2007 г.), на международной конференции "Европейская Комбинаторика" в Севилье (Испания, 2007 г.); на Ломоносовских чтениях в Московском Государственном Университете в 2004 г., а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на Большом семинаре кафедры теории вероятностей механико-математического факультета

МГУ под руководством чл.-корр. РАН А. Н. Ширяева, на семинаре д.ф.-м.н. А. М. Зубкова в МИРАН, на семинаре проф. С. В. Конягина в МГУ, на семинаре проф. Н. Г. Мощевитина в МГУ и др.

Опубликованность результатов

Результаты диссертации опубликованы в работах [35] - [43] списка литературы. Всего по теме диссертации опубликовано 9 работ.

Структура и объем диссертации

В диссертации имеется введение, общая характеристика работы, шесть глав, список литературы. Полный объем 97 страниц, из них 4 страницы занимает список литературы (43 наименования).

Список литературы диссертационного исследования кандидат физико-математических наук Шабанов, Дмитрий Александрович, 2007 год

1. P. Erdos, On a combinatorial problem, 1. Nordisk Mat. Tidskrift, 11(1963), 5-10.

2. P. Erdos, On a combinatorial problem, II, Acta Mathematica of the Academy of Sciences, Hungary, 15(1964), 445-447.

3. J. Beck, On 3-chromatic hypergraphs, Discrete Mathematics, 24(1978), 127137.

4. J.H. Spencer, Coloring n-sets red and blue, J. Combinatorial Theory, Series A, 30(1981), 112-113.

5. J. Radhakrishnan and A. Srinivasan, Improved bounds and algorithms for hypergraph two-coloring, Random Structures and Algorithms, 16(2000), 4-32.

6. A. V. Kostochka, Color-Critical Graphs and Hypergraphs with Few Edges: A Survey, In More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15(2006), 175-198.

7. N. Alon, Hypergraphs with high chromatic number, Graphs and Combinatorics, 1(1985), 387-389.

8. A. V. Kostochka, Coloring uniform hypergraphs with few colors, Random Structures and Algorithms, 44(2003), 166-177.

9. F. Bernstein, Zur Theorie der trigonometrische Reihen, Leipz. Ber., 60(1908), 325-328.

10. E.W. Miller, On a property of families of sets, C. R. Soc. Sci. Varsovie, 30(1937), 31-38.

11. T. R. Jensen and B. Toft, Graph coloring problems, A Wiley-Interscience (1995).

12. J.H. Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289(1985), 679-706.

13. Н. Алон и Дж. Спенсер, Вероятностный метод, М.: Бином. Лаборатория знаний, 2007.

14. P. Erdos and L. Lovasz, Problems and results on 3-chromatic hypergraphs and some related questions, In Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, 11(1975), North Holland, Amsterdam, 609-627.

15. T. Tao and V. Vu, Additive Combinatorics, Cambridge University Press, Cambridge, 2006.

16. Z. Szabo, An application of Lovasz Local Lemma a new lower bound for the van der Waerden number, Random Structures and Algorithms, 1(1990), 344-360.

17. D. Grable, K. Phelps and V. Rodl, The minimum independence number for designs, Combinatorica, 15(1995), 175-185.

18. P. Erdos, Ch. Ко, R. Rado, Intersection theorems for systems of finite sets, J. Math. Oxford, Sec. 12(48)(1961), 313-320.

19. R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Th. Ser. A 76(1996), 121-138.

20. R. Ahlswede, L.H. Khachatrian, The complete intersection theorem for systems of finite sets, Europ. J. Combin. 18(1997), 125-136.

21. M. Deza, P. Frankl, Erdos Ко - Rado theorem - 22 years later, SIAM J. Alg. Disc. Methods 4(1983), 419-431.

22. A. M. Райгородский, Линейно-алгебраичекий метод в комбинаторике, М.: МЦНМО, 2007.

23. P. Erdos, A. L. Rubin and Н. Taylor, Choosability in graphs, In. Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Areata, 1979, Congr. Numer., 26(1980), 125-157.

24. A. V. Kostochka, On a theorem by Erdos, Rubin and Taylor, Electronic Journal of Combinatorics, 9(2002).

25. N. Alon, Choice number of graphs: a probabilistic approach, Combinatorics, Probability and Computing, 1(1992), 107-114.

26. В. Феллер, Введение в теорию вероятностей и ее приложения, Т.1, М.: Мир, 1984.