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

-4Г.__4

Московский государственный университет им. М.В.Ломоносова Механико-математический факультет

На правах рукописи УДК 519 212 2, 519 157

Шабанов Дмитрий Александрович

ВЕРОЯТНОСТНЫЕ МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ О РАСКРАСКАХ РАВНОМЕРНЫХ ГИПЕРГРАФОВ

01.01.05 - теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

э.

003165521

Москва, 2008

Работа выполнена на кафедре математической статистики и случайных процессов Механико-математического факультета Московского Государственного Университета им. М.В Ломоносова

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук Райгородский Андрей Михайлович

доктор физико-математических наук Блиновский Владимир Маркович, кандидат физико-математических наук Виленкин Павел Александрович

Институт системного программирования РАН

Защита диссертации состоит 21 марта 2008 года в 16 часов 45 минут на заседании диссертационного совета Д.501 001.85 в Московском Государственном Университете им. М, В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские Горы, МГУ, механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание МГУ, 14 этаж)

Автореферат разослан 21 февраля 2008 года.

Ученый секретарь диссертационного совета Д.501.001.85 в МГУ, доктор физико-математических наук,

профессор /Ц^ И.Н. Сергеев

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

Актуальность темы.

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

Одним из главных инициаторов применения вероятностного метода в дискретной математике выступил в 50-е годы XX века П Эрдеш, который впоследствии внес в развитие метода очень значительный вклад Его достижения, гипотезы и проблемы в существенной степени стимулировали исследования в этой области

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

Подобные задачи впервые были рассмотрены в работах П Эрдеша Так, в 1960-х гг Эрдешем1 была предложена следующая проблема найти величину т(п, 2), равную минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных двухцветных раскрасок, т е двухцветных раскрасок множества своих вершин, делающих каждое ребро неодноцветным Уже сам Эрдеш использовал вероятностную технику для получения первоначальных результатов относительно поставленной задачи Дальнейшее развитие данная проблема получила в работах таких замечательных специалистов в области вероятностной

»Р Erd6s,0n в combinatorial problem, 1, Nordisk Mat Tidsknft, 11(1963), 5-10

комбинаторики, как Й Бек2, Дж Спенсер3, Дж Радхакришанан и А Срини-вазан4 Ими были построены так называемые рандомизированные алгоритмы раскрасок вершин гиперграфа, с помощью которых и были получены наилучшие известные оценки величины т(п, 2)

Заметим, что свойство гиперграфа, которое фактически фигурирует в определении величины т(п, 2), можно естественно интерпретировать как далеко идущий аналог свойства двудольности обычного графа5 Однако, отнюдь не меньший интерес для исследования представляют многодольные графы Соответственно, и в теории гиперграфов возникают важные обобщения задачи о величине т(п, 2) на случай г-цветных раскрасок

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

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

При изучении раскрасок равномерных гиперграфов особый интерес представляют задачи с дополнительными условиями на пересечения ребер гиперграфа Например, хорошо известна задача о величине т*(п, г)8, равной минимальному числу ребер гиперграфа в классе n-равномерных простых гиперграфов (т е таких гиперграфов, у которых любые два ребра имеют не более одной общей вершины), не допускающих правильных r-цветных раскрасок

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

2J Beck, On 3-ckromatie hypergraphs, Discrete Mathematics, 24(1978), 127-137

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

4 J Radhakrishnan and A Srinivasan, Improved bounds and algorithms for hypergraph two-coloring, Random

Structures and Algorithms, 16(2000), 4-32

6Ф Харари, Теория графов, М КомКнига, 2006

6N Alón, Hypergraphs mth high chromatic number, Graphs and Combinatorics, 1(1985), 387-389

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

8P Erd6s 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

9 A V Kostochka, On a theorem by ErdSs, Rubm and Taylor, Electronic Journal of Combinatorics, 9(2002)

10 A V Kostochka and D R Woodall, Density conditions for panchromatic colourings of hypergraphs, Combinatorics, 21(2001), 515-541

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

Цель работы.

Построение вероятностных алгоритмов раскрасок вершин гиперграфов для доказательства существования раскрасок определенного вида Получение оценок минимального числа ребер гиперграфа в некоторых классах равномерных гиперграфов

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

Основные результаты работы являются новыми и состоят в следующем

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

2 Для характеристики из п 1 найдены нетривиальные верхние оценки

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

4 Улучшены ранее известные нижние и верхние оценки минимального числа ребер гиперграфов в классе п-равномерных гиперграфов, не допускающих радужных трехцветных раскрасок Разработан соответствующий рандомизированный алгоритм раскраски

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

В работе применяются общие методы теории вероятностей, методы исследования вероятностных алгоритмов, теория систем общих представителей

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

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

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

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

Публикации.

Результаты диссертации опубликованы в 9 работах автора, список которых приведен в конце автореферата (см [1]-[9]) Публикаций, сделанных в соавторстве, нет

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

Диссертация состоит из введения, общей характеристики работы, шести глав и списка литературы Общий объем диссертации - 97 страниц Список литературы содержит 43 наименования Нумерация теорем в автореферате совпадает с нумерцией в диссертации

Краткое содержание диссертации.

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

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

Первая глава состоит из шести параграфов В параграфе 1 1 приводится история классической задачи о величине то(п, г), равной минимальному числу ребер гиперграфа в классе п-равномерных гиперграфов, не допускающих правильных г-цветных раскрасок В частности, значительное внимание уделяется величине тп1(п) = т(п, 2)

Параграф 1 2 посвящен одному из основных свойств гиперграфов, рассматриваемых в диссертации, - так называемому свойству Дь, где к - натуральное число

Определение 2. Гиперграф обладает свойством В^, если существует таг кая двухцветная раскраска множества его вершин, в которой любое ребро гиперграфа содержит не менее к вершин каждого цвета

Задача, которая формулируется в §1 2, состоит в отыскании величины тк(п) 1 равной минимальному числу ребер гиперграфа в классе п-равномерных гиперграфов, не обладающих свойством В^ Отметим, что в этой задаче можно считать, что к является функцией от п и к < в то же время при к = 1 мы возвращаемся к классической задаче о величине т1(п) = т(п,2) Одним из центральных результатов диссертации является теорема 1

Теорема 1. Пусть задана целочисленная функция к — к(п) и число 6 €

"2

Л

(О, (1п2 + |) х) Пусть, кроме того, для числа с > 0 выполнено соотношение

с(1-6)-1 + С-<1 Если функция к удовлетворяет неравенству

к -2 + 25П-11ПП

для всех п > щ, то существует такое натуральное число N0, одинаковое

для всех функций к, удовлетворяющих условию (1), что для любого п > N

о

-M^tólS Го

s/2k=l Ct1

Теорема 1 является прямым следствием теоремы 2, которая также формулируется в §1 2

Теорема 2. Пусть задана целочисленная функция к = к(п), фунция р — р(п), принимающая значения из интервала (0,1), и число S € (0,1) Пусть для всех п, начиная с некоторого ni > 18, выполняются неравенства

Введем для удобства следующие обозначения

, . (п — к + 1)р . . п - к + 1 . . ь_,

= ai(n) = (n-k + Dp-Uv а2 = а2(п) = '

«з = а3(п) = (1 + p)fc-1(l - р)1-*( 1 + 2р)*~\ 71 = 7i(«) = тах(а1аз, а2),

Л Л / \ П - А; , . л /i2 л *+>K*-1)

/Ö3 = /?з(п) = 2fc + 1, 72 = 72Н = ßißißzaze

Если некоторая функция х = х(п) удовлетворяет неравенству

xCfrV-* ((1 - р)п + Р(к - 1)) 71 + х2 (C*lj)2p(2k - 1)22*-2"72 < 1

для всехп, начиная с некоторого Ni, то для всех п > тах(щ, Ni) выполнено тк(п) > х(п)

В свою очередь, теорема 3 дает верхнюю оценку величины т^(п) Теорема 3. Пусть функция к = к(п) удовлетворяет условию к = о( при п оо Тогда существует такая функция ф(п), зависящая только от вида функции к(п), стремящаяся к единице при п —> оо, что

тк(п) < (4)

»=о

Если положить к — 1 в теореме 3, то оценка (4) превратится в наилучшую известную верхнюю оценку классической величины mi(n) — т(п, 2), полученную Эрдешем11 более сорока лет назад Если же положить к = 1 в теореме

nP Erd6s, On a combinatorial problem, II, Acta Mathematica of the Academy of Sciences, Hungary, 15(1964), 445-447

1, то оценка (2), по существу, совпадет с наилучшей известной нижней оценкой того же т(п, 2), принадлежащей Радхакришнану и Сринивазану4 Отметим, что область значений параметра к, в рамках которой выполнена оценка (4), шире области, в рамках которой выполнена оценка (2) Это обусловлено применением технически более сложных методов в последнем случае

В параграфе 1 3 рассказывается о свойстве В^ при к ~ | в терминах задачи об уклонении и приводятся наиболее известные результаты в данной задаче Параграф 1 4 посвящен задачам о свойстве В^ с дополнительными ограничениями на класс рассматриваемых гиперграфов

Определение 3. Пусть К - натуральное число Гиперграф обладает свойством Аь, если любые два его ребра либо имеют не менее Н общих вершин, либо не имеют общих вершин совсем Другими словами, гиперграф Я обладает свойством Ан, если для любых е, / 6 Е{Н) выполнено

|еП/|€{0,М+1, , тт(|е|, |/|)}

Отметим, что свойство А^ глубоко мотивировано задачами экстремальной комбинаторики, связанными с теоремой Эрдеша - Ко - Радо12 Из определения 3 следует, что свойство А\ тривиально, им обладает любой гиперграф Считаем, стало быть, что Ь, > 1 Положим

гПк.кЫ) = гшп{|.Е(Н)| Н - п-равномерный гиперграф, обладающий свойством Аь, но не обладающий свойством В к}

Здесь К, подобно к, является, вообще говоря, функцией от п Величина тк,н{п) существует не при всех соотношениях между Ли к Теорема 4 дает необходимое условие существования п-равномерных гиперграфов, обладающих свойством А/г, но не обладающих свойством Вк

Теорема 4. Пусть гиперграф Н обладает свойством А2к и каждое ребро Н содержит не менее 2к вершин Тогда Н обладает свойством Вк

Из теоремы 4 следует, что при Ъ, > 2к величина т^Дтг) не существует Если же Ъ, < 2к, то легко показать, что

тк,н(п) < С%п_2к+1 (5)

При к < к оценка (5) может быть улучшена Теорема 5. Пусть Н < к, тогда

тк,к{п) < тк-и{п - К)

12P Erdfis, Ch Ko, R Rado, Intersection theorems for systems of finite sets, J Math Oxford, Sec 12(48)(1961), 313-320

Если для — к) выполнены условия теоремы 3, то из теоремы 5

вытекает следующая оценка величины т^^(п) при к < к

тКк(п) < с п2 ,^

71—К

Величина то^Дп), очевидно, не может быть меньше, чем тк(п), при любом к Следующая теорема дает существенно лучшую нижнюю оценку величины тк,к{п), нежели все известные нижние оценки т*(п)

Теорема 6. Пусть число 6 взято из интервала (0,1), с > 0 и функции к — к(п), к = к(п) таковы, что для всех п, начиная с некоторого п^, выполняются неравенства

Ш

с + <?( 1 - 6)~2 < 1, (5к - 2)(к - 1) <-Ц-Чп - 6к + 3)

Тогда, если к < 2к, то существует такое натуральное N2, зависящее только от вида функций к(п),к(п), что для всех п > тах(ЛГ2, пг) выполнено неравенство

, ( Згг V 2п-з

В доказательстве теоремы 6 используется следующая общая теорема о нижней оценке величины mj^n)

Теорема 7. Пусть функция к — к(п) удовлетворяет условию к — о(п) при п —у оо, а функция к = к(п) - условию к < 2к Рассмотрим функции х = х(п) и р — р(п) Предположим, во-первых, что множество значений функции р(п) принадлежит (0,1) и выполнено условие р(п) = о(1) при п —> оо Обозначим через А\, Ai, А$ и А4 следующие выражения

A,t = (1 - р)п~к+1(1 + p)k~l- in_T_fc±Ж1

2п-2к + 2-п(1-рУ л,_ (^у (г - ЦМ)"1,

л4 = 2^-У(1+гУ (-~1г~к + г С1'1\ (1 - , Н{к~1] У2

у У \п-к-2к + 2 п~к) V р(п-к-к+1))

Предположим, далее, что для некоторого числа 5 € (0,1) и для каждого п, начиная с некоторого щ, выполняются неравенства

р2{к-1)(п-к + 1)(1-р)-1 <8, (5к — 2)(к — 1) < &р(п — 6к + 3)

и

XС*"1 (Al + А2 + Аз) + Ai < 1

Тогда существует такое натуральное число N3, зависящее только от вида функций к(п) и р(п), что для каждого п > тах(7Уз, пз) произвольный п-равномерный гиперграф Н — (У, Е), обладающий свойством А/, и удовлетворяющий условию |JE/| < а;(п)2п~1, обладает свойством Вк, и, следовательно, mkfii'n) > х(п)2и~х

В параграфе 1 5 рассматриваются задачи о радужных r-раскрасках (т е радужных раскрасках в г цветов) Через р(п, г) обозначается минимальное число ребер гиперграфа в классе n-равномерных гиперграфов, не допускающих радужных r-раскрасок При г = 2 величины m(n, 2) и р(п, 2) совпадают Используя связь между радужными г-раскрасками n-равномерных гиперграфов и предписанными раскрасками полных r-дольных графов, А Косточка9 обосновал следующие оценки для р(п,г) при г > 2 и п > 2

<p(n,r) <reC2?, (6)

г

где с\ и сг - некоторые абсолютные положительные константы, причем ci < сг Следующие две теоремы дают существенно более точную информацию о поведении величины р(щ г) в случае г = 3

Теорема 8. Существует такая функция ф(п), стремящаяся к единице при п —> оо, что выполнено неравенство

, n2eln3 /3\п , . ,

P(n,3)<—jj— (jj Ф(п)

Теорема 9. Существует такая константа с > 0, что для любого п имеет место неравенство

Из теорем 8 и 9 следует, что р(п, 3) = e(3inf+o(i))| Таким образом, зазор между ci и с2 в (6) устранен Теорема 9 следует из теоремы 10 о нижней оценке величины р(п. 3)

Теорема 10. Пусть для некоторой функции х — х{п), для функции р = р(п) со множеством значений из полуинтервала [0, и для любого п выполняется неравенство

81

®(1 - р)п + 21_na;(l + р)п + х2—р{ 1 +р)п~1 < 1

Тогда для всех п справедлива оценка р(п, 3) > х(п)^~

В последнем параграфе первой главы (параграф 1 6) рассматриваются задачи о подгиперграфах

Определение 4. Гиперграф Н\ — (Vi, Е{) называется подгиперграфом гиперграфа Н = (V, Е), если Vi С V, & Ei С Е Подгиперграф Hi называется остовным, если Vi = V

Предположим, что гиперграф не обладает свойством 2?&, но, удалив из него небольшое количество ребер, можно получить новый гиперграф (остов-ный подгиперграф), уже обладающий свойством В к Возникает вопрос каково минимальное число ребер в гиперграфах, в которых подобную операцию провести невозможно? Здесь есть несколько подходов

Первый подход заключается в том, что удалять можно не более, чем е-долю от общего числа ребер Получаем определение свойства Bk¿

Определение 5. Гиперграф Н — (V, Е) обладает свойством В^е, если существует (остовный) подгиперграф Н' = (V, Е'), обладающий свойством Вк, с условием \Е'\ > (1 — е)\Е\ Положим

тк,е(п) = тт{|1?(Я)| Н - n-равномерный гиперграф, не обладающий СВОЙСТВОМ Вк,е}

Из определения видно, что параметр е лежит в пределах от 0 до 1 При £ = 0 свойство Вк,е эквивалентно свойству Вк В то же время при больших е свойство Вк,е становится тривиальным Теорема 11. Пусть

тогда произвольный п-равномерный гиперграф обладает свойством Вк,е

Очевидно, что при любых значениях ей к выполняется неравенство тк,е > гпк(п) Следующая теорема дает лучшую нижнюю оценку тк,е, чем все известные нижние оценки величины тпк(п)

Теорема 12. Обозначим через Л = А(п) следующее выражение

2„-1

Х — е

к-1

Е<?п

t=0

Пусть дано число 5 6 (0,1) и число с € (0, |(1 — <5)) Пусть также для всех п > Гц выполняются неравенства

ft-l<- ¿МсА)

- 1-2^' п

11п(сА)| < Inn — 3 In Inn = ip{n) — ip

Тогда существует такое натуральное число N4, что для всех п > ÍV4 выполняется неравенство

/ ч л, « / n п Ь e~k22~2k 2n_1 m*(») > (1 - 2с(1 -

^ п

1=0

Теорема 12 является прямым следствием теоремы 13, которая также формулируется в §1 6

Теорема 13. Пусть задана целочисленная функция к = к(п), фунция р = р{п), принимающая значения из интервала (0,1), и число S 6 (0,1) Пусть для всех п, начиная с некоторого > 18, выполняются неравенства (S) из условия теоремы 2 Далее, пусть величины 71 = 7i(n) и 72 — те же, что и в условии теоремы 2 Если некоторая функция х — х(п) удовлетворяет неравенству

с*-121-п ((1 _ р)п + p(k _ 1)} 71 + ж {Ct\fp{2k - 1)22А-2"72 < е

для всех п, начиная с некоторого N5, то для любого п > max(ri5, N5) выполнено т^е(п) > х(п)

Второй подход к задаче о подгиперграфах заключается в том, что количество ребер, которые разрешается удалять, предполагается меньшим фиксированного числа I Получаем двупараметрическое свойство F^j гиперграфов Определение 6. Гиперграф И = (У, Е) обладает свойством Fkj, если существует подгиперграф Н' = (V, Е'), обладающий свойством Bf¡, с условием \Е'\ > \E\-l Определим величину fk,i{n), как минимальное число ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Fk¡i

Легко доказать следующие соотношения между тк(п) и fk,i{n)

тпк(п) + 1-1< fk,i(n) < 1тпк{п)

В отличие от предыдущих случаев, вопрос о минимальном числе вершин гиперграфа в данном классе гиперграфов имеет нетривиальный ответ Обозначим через fh{n) минимальное число вершин гиперграфа в классе п-равно-мерных гиперграфов, не обладающих свойством Fk,i Точное значение величины /£г(п) найдено в теореме 14 Теорема 14.

{/ mm(fc-l,i) юш(И,а) \

\j=max(0 ,п-а) j=max(0 ,п—Ь) J

Во второй главе доказываются теоремы 1 и 2 о нижней оценке величины тпк(п) В доказательстве теоремы 2, которое излагается в параграфе 2 1, используется вероятностный метод, связанный с применением нового алгоритма случайной раскраски вершин гиперграфа, построение которого основано на нетривиальном развитии идей из работы Радхакришнана - Сринивазана4 Данный алгоритм допускает следующую вероятностную интерпретацию, которая также приводится в §2 1 (пункт 212)

Пусть Я = (У, Е) - произвольный п-равномерный гиперграф Тогда без ограничения общности можно считать, что V = {1, . ,ю},Е={е 1, , е,п}, причем и) < тп Пусть на некотором вероятностном пространстве (П, Л, Р) заданы бернуллиевские случайные величины , щ, ,Т)Ш и случай-

ный вектор <г = (ах, ,сгщ), принимающий значения в группе перестановок множества V Здесь Р(£, = 1) = Р (£, = 0) = Р(г}г — 1) = р, Р (?}, = 0) = 1 — р (см теорему 2) для любого г = 1, , ад Далее, Р(<т — = («1, ,ги>)) = для любой перестановки («1, ,гю) € вы. При этом случайные величины , тц, , независимы в совокупности, и, бо-

лее того, для любого подмножества В С {0,1}2ш и любой перестановки (гх, , г,„) £ Б-и, выполнено

Р(($ъ . »/ш) е В, о-= (гь ,гш)) =

и>'

те вектор сг "не зависит" от совокупности {^1, ,£«,,»71, ,Существование такого вероятностного пространства очевидно Для каждого г € V положим

а = U {= > «-.к.+£ я** < - %)) >

> п - fc |и = 0} ^С7^ ^ ^К1 - +

+ ^ < а'КХ - 6)(1 -r?s) >n-fci€^

«бе.

/t = 6 + qJ{A} mod 2,

где J - индикатор события

Вектор / = (/х, , fw) можно итерпретировать как случайную двухцветную раскраску множества V (например, полагая /г = 1 тогда и только тогда, когда вершина г покрашена в красный цвет) Если удастся показать, что

Р (У7 = 1, ,тп Л<53/,<п-*;) >0,

V )

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

Теорема 2*. Пусть заданы целые числа п, к < числа р, 6 из интервала (0,1) Пусть величины щ, ач, аз, 71, ¡3\, ¡5%, 0з, 72 те же, что и в условии теоремы 2 Пусть выполняются неравенства

к 1 < 5ПР г?п<1

Тогда для любой системы п-элементных подножеств ,ет множества V = {1,2, , тп} имеет место оценка

¡л=1 I в€е,

< тС„ 2 ((1 - рТ + Р(к - 1)) 71+

/

+т2 (С£})'р(2к - 1)22к~2пу2 (7)

Большая часть §2 1 посвящена доказательству неравенства (7) В доказательстве применяются различные соображения комбинаторного характера, а также оценки вероятностей больших уклонений

В параграфе 2 2 осуществляется вывод теоремы 1 из теоремы 2

В третьей главе доказывается теорема 3 о верхней оценке величины т^п) Доказательство теоремы основано на методах теории систем общих представителей^

В четвертой главе доказываются теоремы 4 - 7 о различных оценках величины т^/,(п) Наиболее сложным является доказательство теоремы 7, которое приводится в параграфе 4 1 Оно основано на применении вероятностного метода, связанного с построением нового алгоритма случайной раскраски вершин гиперграфа Похожий алгоритм строился во второй главе при доказательстве теоремы 2 Тем не менее, здесь имеются некоторые отличия

13А М Райгородский, Системы общих представителей, Фундам и прикл мат, Т5, Вып 3(1999), 851-860

Н Н Кузюрин, Асимптотическое исследование задачи о покрытии, Проблемы кибернетики, Вып 37(1980), 19-56

Пусть, без ограничения общности, гиперграф Н — (V, Е), обладающий свойством Ад, таков, что V = {1, , и/}, Е — {ег, ,ет}, причем и> < тп Далее, пусть на некотором вероятностном пространстве (О, Л, Р) заданы независимые в совокупности бернуллиевские случайные величины , щ, ,7?«, Здесь Р(£, = 1) = Р(г), = 1 )=р Для каждого г € V положим

Д = (J ел

3

и

/, = 6+чЛД} mod 2 Вектор / = (fi, ,fw) можно интерпретировать как случайную раскраску множества V Если удастся показать, что

plvj = l, ., т > О,

V sSeJ /

то это будет означать, что гиперграф Н обладает свойством В& В пункте 412 формулируется теорема об оценке вероятности противоположного события, из которой легко получить теорему 7

Теорема 7*. Пусть функция к = к{п) удовлетворяет условию к — о(п) при п —>• оо, а функция h = h(n) - условию h < 2k Пусть также задана функция р = р(п), число 6 из интервала (0,1) и натуральное число х Предположим, что множество значений функции р(п) принадлежит (0,1) и выполнено условие р{п) = о(1) при п оо Пусть величины А\, Аз, A3, Aj те же, что и в условии теоремы 7 Если для всех п, начиная с некоторого n¡, выполняются неравенства

(Ък — 2)(к — 1) < ip(n-6fc + 3), — 1)(тг — fc + 1)(1 — J?)-1 <6,

тогда существует такое натуральное число N3, что для любого п > N3 и для любой системы п-элементных подножеств е%, ,ех множества V = = {1,2, , хп}, обладающей, свойством Ah, имеет место оценка

1 J=1 I see,

<xCt1(Ai + A2+As)+A4 (8)

/

Большая часть §4 1 посвящена доказательству неравенства (8) Как и в случае неравенства (7), здесь используются комбинаторные соображения и оценки вероятностей больших уклонений

В параграфе 4 2 теорема 6 выводится из теоремы 7 В параграфе 4 3 строится несложный алгоритм для доказательства теоремы 4 Наконец, параграф 4 4 посвящен доказательству теоремы 5

В пятой главе доказываются теоремы 8-10 об оценках величины р(п, 3) Теорема 8, подобно теореме 3 о верхней оценке величины т,к(п), доказывается в параграфе 5 1с помощью теории систем общих представителей

Нижняя оценка величины р(п, 3), анонсированная в теоремах 9 и 10, получается применением вероятностного метода, основанного на использовании нового рандомизированного алгоритма раскраски вершин гиперграфа (см параграфы 5 2 и 5 3)

Пусть, без ограничения общности, гиперграф H — (V, Е) таков, что V = = {1, , w}, Е — {ei, , em}, причем w < тп Пусть, как и в аналогичных случаях раньше, на некотором вероятностном пространстве (Q, Л, Р) заданы независимые в совокупности случайные величины ,€w>Vh ¡Vw Здесь

= 1) = = 2) = J>(£, = 3) =

Р(ъ = 1) = P(vt = 2) = Р(г,г = 3) = Р, Р(Ъ = 0) = 1 - Зр, где р - некоторое число из интервала (0, Для каждого г € V положим

А= и ûn&

j i€e¡ к=1 s€e3

И

/, = Í, (i - /{Д}/{% ^ 0}) + ч,/{Д}

Легко видеть, что случайная величина /, принимает только значения 1, 2 или 3 Поэтому вектор f — (jfij т fu;) можно итерпретироватъ как случайную трехцветную раскраску множества V (например, полагая /, = 1 тогда и только тогда, когда вершина г покрашена в красный цвет) Если удастся показать, что выполнено неравенство

(т 3 \

3=1 к=1 see, )

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

Теорема 10*. Пусть дано число р из полуинтервала [0,|) Тогда для любой системы п-элементных подножеств ei, ,ет множества V =

= {1,2, ,тп} имеет место оценка

В параграфе 5 3 теорема 9 выводится из теоремы 10 Шестая глава посвящена доказательствам результатов в задачах о под-гиперграфах

Теорема 11 доказывается в параграфе 6 1 несложным вероятностным методом Доказательства теорем 12,13 об оценках величины ть,Е(п) изложены в параграфах 6 2, 6 3 и основаны на оценке математического ожидания случайной величины Х(/), равной количеству ребер, содержащих необходимое число вершин каждого цвета в случайной раскраске / вершин гиперграфа, построенной в рамках рандомизированного алгоритма, приведенного в доказательстве теоремы 2 (вторая глава) В параграфе 6 4 доказана теорема 14

Наконец, в параграфах 6 5 и 6 6 формулируется и доказывается следующая теорема

Теорема 15. Пусть фиксированы натуральные числа I, п,к,у и число /3 > 1 Введем обозначения

(тш(£—1,и—а) шт{И,о) \

£ + £ с^ца],

3=тах(0,п—о) ^=тах(0,п—«+а) у

С" Л 2"/(«) Л

Если выполняются неравенства к < | и

~ /?(/?й> + 1)'

тогда существует п-равномерный гиперграф Н, не обладающий свойством Рк,1, с условиями \У{Н)| = V, \Е(Н)\ < 1{Рр0 + 1)

В доказательстве теоремы 15, приведенном в §6 6, используются методы теории систем общих представителей

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

т 3 » о,

и и П {/. * ^ Н - рТ+21""т(1+*)"+™2мр{1+рГ

1=1 к=1 э€е,

Работы автора по теме диссертации

[1] Д. А Шабанов, Об одной комбинаторной задаче Эрдеша, Доклады Академии Наук, 396 N2(2004), 166-169

[2] Д А Шабанов, О раскрасках гиперграфов, Доклады Академии Наук, 402 N5(2005), 605-608

[3] Д А Шабанов, О числе вершин в гиперграфах близких к двудольным, Доклады Академии Наук, 412 N1(2007), 31-34

[4] Д А Шабанов, Экстремальные задачи для раскрасок равномерных гиперграфов, Известия РАН Серия математическая, 71 N6(2007), 183-222

[5] D A Shabanov, On some extremal properties of hypergraphs colorings, Electronic Notes m Discrete Mathematics, 29(2007), 97-100

[6] Д А Шабанов, Об одной комбинаторной задаче Эрдеша, Материалы международной конференции "Дискретный анализ и исследование операций", Новосибирск изд-во института математики (2004), стр 91

[7] D. A Shabanov, On В Property of Hypergraphs, Abstracts of the talks at "Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications", ITI Series, Prague (2006), p 114

[8] D A Shabanov, On Some Properties of Hypergraphs, Abstracts of the talks at "EMS Conference on Horizon of Combinatorics", изд-во Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest (2006), p 59

[9] Д А Шабанов, Об экстремальных характеристиках равномерных гиперграфов, Материалы IX Международной семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О Б Лупанова, Москва изд-во механико-математического факультета МГУ, 2007, стр 256-258

Издательство ДПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать 48 0& Формат 60x90 1/16 Уел печ л -/.О Тираж УОО экз Заказ О1/

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

Введение

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

Глава 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 наименования).

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.