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

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

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

Содержание

Введение

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

Глава 1. Задача Эрдеша — Хайнала о раскрасках гиперграфов

§1.1 История задачи Эрдеша - Хайнала

§1.2 Новые оценки в задаче Эрдеша - Хайнала

§1.3 Доказательство первой оценки в задаче Эрдеша Хайнала

§1.7 Доказательство нижней оценки максимальной степени ребра

в гиперграфах с большим обхватом

§1.8 Задача Эрдеша - Хайнала для предписанных раскрасок

предписанных раскрасок

Глава 2. Задача Эрдеша — Ловаса о раскрасках простых гиперграфов

§2.1 История задачи Эрдеша - Ловаса

§2.2 Новые результаты в задаче Эрдеша - Ловаса

§2.3 Частичные системы Штейнера и /-простые гиперграфы

§2.4 Доказательство оценок величины т*(п, г, I)

§2.5 Оценки максимальной степени вершины в простых гиперграфах с большим хроматическим числом

§2.6 Доказательства нижних оценок в задаче Эрдеша - Ловаса

в простых гиперграфах с большим хроматическим числом

§2.9 Доказательство нижней оценки максимальної'! степени ребра

в (п, /)-систсмах с большим хроматическим числом

Глава 3. Раскраски гиперграфов с большим обхватом

§3.1 Оценки максимальной стегюии вершины в графах и гиперграфах с большим хроматическим числом и большим обхватом

трех

§3.3 Доказательство оценки максимальної! степени ребра в гиперграфах с большими хроматическим числом и обхватом больше

пяти

§3.4 Задача типа Эрдеша - Хайнала для гиперграфов с большим

обхватом

§3.5 Раскраски неоднородных гиперграфов с большим обхватом

Глава 4. Задачи о полноцветных раскрасках гиперграфов и их

приложения

§4.1 Задача Косточки о полноцветных раскрасках гиперграфов

§4.2 Доказательство нижней оценки величины р(п,г)

§4.3 Доказательства верхних оценок величины р(п,г)

§4.4 Достаточное условие существования полноцветных раскрасок . 221 §4.5 Асимптотика предписанного хроматического числа полных многодольных графов

Глава 5. Функция Ван дер Вардена и раскраски гиперграфов 231 §5.1 Теорема Ван дер Вардена об арифметических прогрессиях

Глава 6. Раскраски случайных гиперграфов

§6.1 Общие сведения из теории случайных подмножеств

§6.2 Пороговая вероятность 2-раскрашиваемости случайного гиперграфа

§6.3 Пороговая вероятность г-раскрашиваемости случайного гнпер-

графа

§6.4 Новые нижние оценки пороговой вероятности г-раскрашиваемости случайного гиперграфа

Синеок цитированной литературы

Список работ автора по теме диссертации

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

Введение

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

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

Экстремальные задачи о раскрасках ги пер графов впервые возникли в классических работах 20-30-х годах XX века, положивших начало теории Рамсея. Формально говоря, теория Рамсея — это не теория в общепринятом смысле, а набор различных результатов из анализа, геометрии, комбинаторики, теории чисел и т.д., которые объединены общей философией их восприятия. Основной принцип теории Рамсея можно сформулировать следующим образом:

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

Задачи рамсеевского типа берут свое начало в комбинаторике с теоремы Рамсея 1930 года (см. [1]), в теории чисел — с теоремы Ван дер Вардена 1927 года (см. [2]), в геометрии — с проблем Эрдеша - Секереша, поставленных в 1935 году (см. [3]). Историю задач типа Эрдеша - Секереша, а также последние достижения в этой области можно найти, например, в следующих книгах и обзорах: [4]—[8]. Первые же две теоремы очень тесно связаны с раскрасками гиперграфов и, по сути, стимулировали развитие теории раскрасок гиперграфов.

Теорема Рамсея является глубоким обобщением классического принципа Дирихле, а потому лежит на стыке комбинаторики и логики. Сформулируем данный результат (доказательство которого можно найти, например, в книге [9]) в его максимальной общности. Пусть 5 — множество из п элементов,

обозначим через Ль (5) — множество всех /с-подмножеств множества 5. Пусть также даны натуральные числа ї ^ 2 и ..., с условием ^ к для любого г = 1,...,

Теорема. (Ф. Рамсей, [1]) Существует такое минимальное число і?(йі,..., 5*; что ео/ш п > і? (5ІЗ..., /с), то при любом упорядоченном і-разбие-нии А\ и ... и Аі мнооїсества Рк{$) найдется г и зг-подмпооісество миооїсе-ства Б, все к-подмиолсества которого содероісатся в Аг.

Величину і^яі,..., /г) из теоремы Рамсея принято называть числом Рамсея. Исследование асимптотического поведения числа Рамсея является одной из центральных задач всего комбинаторного анализа. Ее изучению посвящены работы таких классиков комбинаторной математики, как П. Эрдеш, Р. Радо, А. Хайнал, Е. Семереди, Дж. Спенсер, В. Рёдль, а также таких известных математиков, как Я. Комлош, М. Айтаи, Э. Томасон, Дж. Ким и др. В последнее десятилетие различные оценки чисел Рамсея были получены Д. Конлоном, Дж. Фоксом, Б. Судаковым, Т. Боманом, П. Кивашем. Подробнее с результатами вышеперечисленных авторов можно ознакомиться в статьях [101-124].

В настоящее время существует огромное количество различных обобщений задачи о числе Рамсея. Все задачи такого типа наиболее удобно формулировать в терминах реберных раскрасок графов и гиперграфов. Например, если к = 2 и = ... = = 5, то величину Щв,..., в] 2) можно определить следующим образом: это такое минимальное натуральное число, что если п ^ Я (з,..., 5; 2), то в любой ¿-цветной раскраске множества ребер полного графа Кп на п вершинах найдется полностью одноцветный полный подграф К8 на в вершинах. Кроме того, несложно понять, что неравенство п < І? (в,..., й; 2) эквивалентно существованию правильной раскраски в і цветов для однородного гиперграфа специального вида, вершинами которого являются ребра Кп, а ребрами — те наборы ребер графа КП) которые вместе образуют полный подграф К3. Отметим, что именно с помощью абстрактных результатов теории раскрасок гиперграфов доказывается наилучшая на сегодняшний день нижняя асимптотическая оценка величины ..., 5; 2). Задачи рамсеевского типа — это неотъемлемая часть современной теории графов, очень тесно связанная с экстремальными задачами о раскрасках гиперграфов.

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

Теорема. (Б. Ван дер Варден, [2]) Для любых натуральных чисел п ^ 3 и г ^ 2 существует такое минимальное число IV(п, г), что для каоїс-

дого натурального N ^ W(n,r) в любой г-цветной раскраске множества {1,2,..., N} найдется одноцветная арифметическая прогрессия длины п.

Несмотря на кажущуюся простоту и естественность, теорема Ван дер Вар-дсна сыграла значительную роль в развитии двух разделов математики — аддитивной комбинаторики и комбинаторной эргодической теории. Эти две области математики связаны между собой теснейшим образом и находятся на стыке таких наук, как аддитивная и аналитическая теория чисел, теория графов и теория динамических систем. Подробнее о многообразии результатов, так или иначе связанных с теоремой Ban дер Вардена и ее обобщениями, можно прочитать, например, в обзорах [25], [26].

Величина W(n,r) из теоремы Ban дер Вардена называется функцией Ван дер Вардена. Задача о нахождении функции Ban дер Вардена — классическая проблема аддитивной комбинаторики, ее асимптотическому исследованию посвящены работы таких известных математиков, как П. Эрдеш, Р. Радо, В.М. Шмидт, Э. Берлекамп, С. Шелах, 3. Сабо, Т. Гауэрс и др. Как, и в случае чисел Рамсея, определение функции Ван дер Вардена также может быть переформулировано в терминах раскрасок гиперграфов. Подробнее эта задача будет обсуждаться в пятой главе диссертации, в которой с помощью метода случайной перекраски получена новая асимптотическая нижняя оценка W(n,r): существенно улучшающая почти все предыдущие результаты.

Проблемы теории Рамсея в существенной степени инициировали исследования в области раскрасок гиперграфов. Однако определения правильной раскраски и хроматического числа для гиперграфов были перенесены из теории графов далеко не сразу. Напомним, что раскраской множества вершин графа G = (V, Е) называется произвольное отображение / : V —» С, где С — некоторое множество, называемое множеством цветов. Если \С\ = г, то раскраска / называется r-цветной или r-раскраской. Раскраска множества вершин V графа G называется правильной, если в этой раскраске вершины, соединенные ребром, покрашены в разные цвета. Хроматическим числом графа G называется минимальное число цветов, требуемое для правильной раскраски множества его вершин. Хроматическое число графа G принято обозначать через x(G)- Если x(G) ^ г, т.е. для графа G существует правильная раскраска вершин в г цветов, то G является r-раскрашиваемым. Граф G называется двудольным, если он является 2-раскрашиваемым.

Двудольность гиперграфов долгое время изучалась с использованием термина свойство В, введенного Э. Миллером в 1937 году (см. [27]). Согласно определению Миллера гпперграф II — (V, Е) обладает свойством В, если существует такое подмножество S С V, что для любого с G Е выполнены два

свойства:

eU и e£S.

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

Понятие же правильной раскраски графа можно обобщать по-разному на гиперграфы. Первое естественное определение — это считать раскраску множества вершин гиперграфа Н = (V, Е) правильной, если в ней любые две вершины, содержащиеся в одном ребре, покрашены в разные цвета. Такие раскраски гиперграфа принято называть сильными (в англоязычной литературе также используется термин rainbow colorings). Минимальное же число цветов, требуемое для сильной раскраски множества вершин гиперграфа II, принято называть сильным хроматическим гиперграфа Н. Однако, понятие сильной раскраски не вносит в теорию гиперграфов ничего принципиально нового по сравнению с графами: сильная раскраска вершин гиперграфа Н — (V, Е) есть не что иное, как правильная раскраска вершин вспомогательного графа G — (V, Ei), в котором две различные вершины смежны тогда и только тогда, когда они имеют общее ребро в гиперграфе II. Сказанное, впрочем, не означает бесполезности понятия сильной раскраски ввиду связи его с некоторыми другими свойствами гиперграфа, уже не сводимыми (или сводимыми существенно иным путем) к свойствам графов (подробнее, см. [28], [29], [30]).

Гораздо более глубокое понятие правильной раскраски гиперграфа было предложено П. Эрдеиюм и А. Хайналом в 1966 году в работе [31]. Согласно их определению раскраска множества вершин V гиперграфа II — (V, Е) называется правильной, если в этой раскраске все ребра из Е(Н) не являются одноцветными (т.е. содержат вершины разных цветов). Хроматическим числом гиперграфа II называется минимальное число цветов, требуемое для правильной раскраски вершин этого гиперграфа. Мы будем обозначать хроматическое число гиперграфа Н через х(Ю- Если х(Ю ^ г, т.е. для гиперграфа Н существует правильная раскраска вершин в г цветов, то говорят, что Н является r-раскрашиваемым. Подобное определение хроматического числа гинерграфа очень хорошо сочетается с другими характеристиками гиперграфа (число независимости, максимальная степень вершины и т.п.), позволяя сохранить ту же самую взаимосвязь между ними, что и в обычных графах. Как и для графов, с точки зрения вычислений проблема г-раскрапшваемости гиперграфа в общем случае является NP-полной, а проблема нахождения хроматического числа — NP-трудной (см., например, [32]). В связи с этим естественным образом возник вопрос о нахождении легко проверяемых до-

статочных условий г-раскрашиваемости гинерграфа.

Одной из первых возникших на этом пути задач явилась экстремальная задача Эрдеша и Хайнала о раскрасках гиперграфов, впервые поставленная наш в 1961 году в работе [33]. Проблема состоит в том, чтобы найти величину т(п), равную минимально возмоэ/сному количеству ребер гиперграфа в классе п-одиородиых гиперграфов, не являющихся 2-раскрашиваемыми. Данная проблема естественным образом обобщается на случаи гиперграфов с большим хроматическим числом: отыскать величину т(п,г), равную минимально возмоэюиому числу ребер гиперграфа в классе п-одпородиых гиперграфов, не являющихся г-раскрашиваемыми. Несмотря на простоту формулировки, задача о нахождении величины т(п,г) до сих пор не решена при п ^ 3 (в том время, как в случае графов, п = 2, она представляет собой несложное упражнение для школьников). Проблема Эрдеша Хаииала — это, несомненно, центральная задача теории раскрасок гиперграфов. В настоящее время существует огромное количество ее обобщений для различных классов гиперграфов и видов раскрасок, по сути можно говорить о целом направлении в экстремальной комбинаторике, связанном с этой задачей. Результаты относительно задачи Эрдеша - Хайнала и ее обобщений нашли применение в теории Рамсея, теории графов, аддитивной комбинаторике, теории случайных гиперграфов. Экстремальным задачам о раскрасках гиперграфов посвящены работы таких классиков комбинаторики, как П. Эрдеш, А. Хайнал, II. Алон, Дж. Спенсер, J1. Ловас, П. Сеймур, Й. Бек, В. Рёдль, Б. Боллобаш, а также таких известных математиков, как А. В. Косточка, Д. Мубаи, А. Фриз, П. Тетали, 3. Сабо, Дж. Радхакрпшнан, А. Сринивасан, А. Плухар и др.

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

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

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

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

Экстремальные задачи о раскрасках гиперграфов в соответствии с изложенной выше условной классификацией проблем вероятностной комбинаторики можно отнести ко второй группе. Однако вероятностные методы и техники, появившиеся в результате изучения этих задач, в дальнейшем стали одними из важнейших инструментов комбинаторики в целом. Первым подобным инструментом стала чисто вероятностное утверждение об оценке вероятности одновременного невыполнения набора событий в условиях малого числа зависимостей, получившее название "Локальная лемма" и доказанное Л. Ловасом в его знаменитой совместной работе с Эрдсшем [34] в 1973 году. Первым применением Локальной леммы явилась первая нетривиальная нижняя оценка максимально!"! степени ребра в однородном гиперграфе с большим хроматическим числом. Однако ее универсальность и простота в применении оказались востребованы во многих других областях математики.

Сегодня Локальная лемма активно используется не только в комбинаторике, но и в многих других областях математики (таких, например, как теоретическая информатика, теория чисел и т.д.). Из недавних ярких результатов, полученных с помощью Локальной леммы отмстим теорему Л. Лу и Л. Се-кеи (см. [35]), обобщающую знаменитую теорему Хайнала - Семереди (см. [36]) о "справедливых"1 раскрасках обычных графов на случай однородных гпперграфов.

Второй замечательной вероятностной техникой, получившей качественное развитие в задачах о раскрасках гиперграфов, является "полуслучайный" метод (в зарубежной литературе принято название semi-random или nibble метод). Впервые основные идеи этого метода появились в работе М. Айтаи, Я. Комлоша, Дж. Пиица, Дж. Спенсера и Е. Семереди [37) 1972 года для получения нижней оценки числа независимости однородного гиперграфа с ограниченной максимальной степенью вершины и большим обхватом. В дальнейшем их вероятностная техника была существенно доработана В. Рёдлем (см. [38]) в 1985 году для доказательства знаменитой гипотезы Эрдеша - Ханани (см. [39]) о минимальных (п, /с, ^-конфигурациях. Данная область комбинаторной математики тесно связана с асимптотическими вопросами теории кодирования, проблемами о, так называемых, упаковках и покрытиях. В теории же раскрасок графов и гиперграфов полуслучайный метод получил качественное развитие. Так, например, в 1995-96 годах с его помощью Дж. Иоханссеном и Дж. Кимом (см. [40], [41]) были получены асимптотически неулучшаемыс оценки хроматического числа графов с большим обхватом в зависимости от максимальной степени вершины. Кроме того, сочетая данный метод с применением Локальной леммы и других вероятностных инструментов, Д. Мубаи и А. Фриз (см. [42)) получили в 2008 году гораздо более сильный результат, нежели Айтаи, Комлош и их соавторы, о верхней оценке хроматического числа простого гиперграфа с ограниченной максимальной степенью вершины (подробнее данный результат будет обсуждаться в §2.5 диссертации).

Наконец, еще одним достижением вероятностных исследований в области раскрасок гиперграфов является метод случайной перекраски. Данный метод в комбинаторной форме был впервые предложен И. Беком (см. [43]) в связи с задачей Эрдеша - Хайнала о величине т{п). В дальнейшем, метод случайной перекраски развивался в работах Дж. Спенсера, Дж. Радхакриш-пана, А. Сринивасана, 3. Сабо, A.B. Косточки, М. Кумбхата и зарекомендовал себя, как один из наиболее эффективных инструментов в экстремальных задачах о раскрасках гиперграфов. В диссертации предложены оригиналь-

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

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

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

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

Цель работы

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

• исследование задачи Эрдеша - Хайнала о раскрасках гиперграфов,

• исследование задачи Эрдеша - Ловаса о раскрасках простых гиперграфов,

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

• исследование поведения предписанных хроматических чисел полных многодольных графов с одинаковым размером долей,

• асимптотическое исследование функции Ван дер Вардена.

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

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

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

2. Получена новая нижняя оценка максимальной степени вершины /¿-однородного гиперграфа с хроматическим числом больше г.

3. Доказаны новые нижние оценки в задаче Эрдеша - Ловаса о минимальном числе ребер гиперграфа в классе п-однородных простых гиперграфов с хроматическим числом больше г.

4. Обоснованы новые верхние и нижние оценки минимально возможного числа ребер гиперграфа в классе (п, ¿)-систем с хроматическим числом больше г.

5. Получены новые нижние оценки максимальной степени вершины п-одно-родного простого гиперграфа с хроматическим числом больше г.

6. Получена новая нижняя оценка максимальной степени ребра в (п, /)-системе с большим хроматическим числом.

7. Обоснована новая нижняя оценка максимальной степени вершины гиперграфа в классе п-однородных гиперграфов с большим хроматическим числом и обхватом больше 3.

8. Обоснованы новые нижние оценки максимальной степени вершины и количества ребер гиперграфа в классе п-однородных гинерграфов с большим хроматическим числом и обхватом больше 5.

9. Получено новое достаточное условие г-раскрашиваемости неоднородного гиперграфа Н = (V, Е) с обхватом больше 3 в терминах ограничения на функцию /г(Я) - £ г1-|е|.

е£Е

10. Доказаны новые нижние оценки в задаче Косточки о минимально возможном количестве ребер гиперграфа в классе п-однородных гиперграфов, не допускающих полноцветных г-раскрасок.

11. Найдена асимптотика предписанного хроматического числа полного г-дольного графа Кт*г с равным размером долей т в значительно более широкой области значений параметров \пг = о(1пто).

12. Обоснованы новые асимптотические нижние оценки функции Ван дер Вардена.

13. Найдены новые нижние оценки пороговой вероятности г-раскрашиваемости случайного гиперграфа.

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

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

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

теория систем представителей. Доказательства основных результатов опираются на новые модификации метода случайной перекраски Бека - Спенсера.

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

Диссертация носит теоретический характер. Результаты и методы работы могут быть полезны в исследованиях задач экстремальной и вероятностной комбинаторики, теории графов и теории Рамсея, связанных с раскрасками гиперграфов. Они могут быть интересны специалистам, работающим в МГУ имени М.В.Ломоносова, МИРАН им. В.А. Стеклова, ИППИ РАН им. A.A. Харкевича, МФТИ, ИСП РАН и других высших учебных заведениях и научных центрах страны. Результаты диссертации могут составить содержание специальных курсов для студентов и аспирантов.

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

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

1. «Большой семинар кафедры теории вероятностей», механико-математический факультет МГУ имени М.В.Ломоносова, руководитель — академик РАН А.Н. Ширяев (сентябрь 2010, ноябрь 2010, октябрь 2011).

2. «Семинар Добрушинской математической лаборатории», Институт проблем передачи информации им. A.A. Харкевича РАН, руководитель — профессор P.A. Минлос (январь 2012).

3. Семинар «Теория вероятностей и статистическая физика», механико-математический факультет МГУ имени М.В.Ломоносова, руководители — профессор Б.М. Гуревич, профессор В.И. Оселедец, профессор С.А. Пирогов (ноябрь 2011).

4. «Семинар отдела дискретной математики МИАН», Математический институт им. В.А. Стеклова РАН, руководитель — д.ф.-м.н. A.M. Зубков (март 2011).

5. Семинар «Математические вопросы кибернетики», механико-математический факультет МГУ имени М.В.Ломоносова, руководитель — профессор О.М. Касим-Заде (ноябрь 2010).

6. «Кафедральный научно-исследовательский семинар» кафедры анализа данных ФИВТ МФТИ, руководитель — профессор A.M. Раигородский (октябрь 2008, декабрь 2008, март 2009, ноябрь 2009, март 2010).

7. Семинар «Дискретный анализ», факультет ВМиК МГУ им. M.B. Ломоносова, руководитель — профессор A.A. Сапоженко (декабрь 2008, октябрь 2010, декабрь 2011).

8. Семинар «Ортогональные ряды», механико-математический факультет МГУ имени М.В.Ломоносова, руководители — академик РАН B.C. Кашин, член-корр. РАН C.B. Конягип (март 2009, ноябрь 2009).

9. «Семинар по теории кодирования», Институт проблем передачи информации им. A.A. Харкевича РАН, руководитель — д.ф.-м.н. Л.А. Басса-лыго (февраль 2008, декабрь 2010).

10. «Московский семинар по теории чисел», механико-математический факультет МГУ имени М.В.Ломоносова, руководители — член-корр. РАН Ю.В. Нестеренко, профессор Н.Г. Мощевитин (март 2011).

11. Семинар «Избранные вопросы алгебры », механико-математический факультет МГУ имени М.В.Ломоносова, руководители — профессор В.Н. Латышев, профессор A.B. Михалев (декабрь 2010).

12. Межуниверситетский берлинский семинар «Methods for discrete structures» (Технический Университет, Свободный Университет, Университет им. А. Гумбольдта), г. Берлин, Германия, руководители — профессор M Скутелла, профессор Г. Циглер (январь 2011).

13. Семинар «Combinatorics Seminar», Свободный Университет г. Берлин, Германия, руководитель — профессор Т. Сабо (январь 2011, январь 2012).

14. «Семинар по дискретной математике», Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН, руководитель — академик РАН Ю.В. Матиясевич (сентябрь 2011).

15. Семинар «Арифметика и геометрия», механико-математический факультет МГУ имени М.В.Ломоносова, руководители — профессор Н.Г. Мощевитин, профессор A.M. Райгородский (ноябрь 2008, октябрь 2009, ноябрь 2010).

16. Семинар «Алгебраическая топология и ее приложения», механико-математический факультет МГУ имени М.В.Ломоносова, руководитель — член-корр. РАН В.М. Бухштабер (октябрь 2011).

17. Семинар «Алгоритмические вопросы алгебры и логики», механико-математический факультет МГУ имени М.В.Ломоносова, руководитель — академик РАН С.И. Адян (октябрь 2011).

18. Семинар «Современные проблемы теории чисел», Математический институт им. В.А. Стеклова РАИ, руководители — член-корр. РАН C.B. Конягин, д.ф.-м.н. И.Д. Шкредов (май 2011, декабрь 2011).

Кроме того, результаты диссертации также были представлены на следующих международных конференциях:

1. Fete of Combinatorics and Computer Science, Кестхей, Венгрия, 11 - 15 августа 2008 г.

2. Восьмая международная конференция Дискретные модели в теории управляющих систем, Москва, 06 - 09 апреля 2009 г.

3. European Conference on Combinatorics, Graph Theory and Applications (EuroComb'09'), Бордо, Франция, 07 - 11 сентября 2009 г.

4. X международный семинар Дискретная математика и ее приложения, Москва, 01 - 06 февраля 2010 г.

5. 8th French Combinatorial Conference, Opee, Франция, 28 июня - 02 июля 2010 г.

6. 15th conference on Random Structures and Algorithms, Атланта, США, 24 - 28 мая 2011 г.

7. Infinite and finite sets, Будапешт, Венгрия, 13 июня - 17 июня 2011 г.

8. European Conference on Combinatorics; Graph Theory and Applications (EuroComb'll), Будапешт, Венгрия, 29 августа - 02 сентября 2011 г.

9. Восьмая международная Петрозаводская конференция Вероятностные методы в дискретной лштемагпике, Петрозаводск, 02 - 09 июня 2012 г.

Публикации

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

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

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

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

Список цитированной литературы

[1] F. P. Ramsey, "On a problem of formal logic", Proc. of London Math. Society Scr. 2, 30 (1930), 264-28G.

[2] B. L. van der Waerden, "Beweis einer Baudetschen Vermutung", Nieuw Archief voor Wiskundc, 15 (1927), 212-216.

[3] P. Erdos, G. Szekeres, "A combinatorial problem in geometry", Compositio Math., 2 (1935), 463 -470.

[4] P. Грэхем, Начала теории Рамсея, Мир, М., 1984.

[5] R. L. Graham, В. L. Rotshild, J. II. Spencer, Ramsey theory, 2nd edition, Wiley, New York, 1990.

[6] W. Morris, V. Soltan, "The Erdos - Szekeres problem on points in convex position", Bulletin of the American Mathematical Society, 37:4 (2000), 437 - 458.

[7] P. Brass, W. Moser, Л. Pach, Research problems in discrete geometry, Springer, 2005.

[8] В. А. Кошелев, A. M. Райгородский, "Задача Эрдеша Секерсша о выпуклых многоугольниках", Квант, 2 (2009), 6-13.

[9] К. А. Рыбников, Введение в комбинаторный анализ, Изд-во Московского Университета, Москва, 1972.

[10] P. Erdos, "Some remarks on the theory of graphs", Bull. American Math. Society, 53 (1947), 292-294.

[11] P. Erdos, R. Rado, "Combinatorial theorems on classifications of subsets of a given set", Proc. London Math. Soc., 3:2 (1952), 417-439.

[12] P. Erdos, A. Ilajnal, R. Rado, "Partition relations for cardinal numbers", Acta Mathematica of the Academy of Sciences, Hungary, 16 (1965), 93-196.

[13] J. H. Spencer, "Ramsey's theorem — a new lower bound", Journal of Combinatorial Theory, Ser. A, 18 (1975), 108-115.

[14] Л. H. Spencer, "Asymptotic lower bounds for Ramsey functions", Discrete Mathematics, 20:1 (1977/78), 69-76.

[15] M. Ajtai, Л. Komlos, E. Szemeredi, "A note on Ramsey numbers", J. Combinatorial Theory. Ser. A, 29 (1980), 354-360.

[16] R. L. Graham, V. Rodl, "Numbers in ramsey theory", Surveys in Combinatorics, London Math. Soc. Lecture Note Series no. 123, Cambridge Univ. Press, 1987, 111-153.

[17] A. Thomason, "An upper bound for some ramsey numbers", Journal of Graph Theory, 12 (1988), 509-517.

[18] P. Erdos, A. Hajnal, "Ramsey-type theorems", Discrete Appl. Math, 25:1-2 (1989), 37-52.

[19] D. Duffus, H. Lefmann, V. Rodl, "Shift graphs and lower bounds on Ramsey numbers г^(1: г)", Discrete Mathematics, 137 (1995), 177-187.

[20] J. H. Kim, "The Ramsey number R(3,t) has order of magnitude £2/logi", Random Structures and Algorithms, 7:3 (1995), 173-207.

[21] D. Conlon, "A new upper bound for diagonal Ramsey numbers", Annals of Mathematics, 70 (2009), 941-960.

[22] T. Bohman, "The Triangle-Free Process", Advances in Mathematics, 221 (2009), 1653-1677.

[23] D. Conlon, J. Fox, B. Sudakov, "Hypergraph Ramsey numbers", Journal of the American Mathematical Society, 23:1 (2010), 247-266.

[24] D. Conlon, Л. Fox, B. Sudakov, "An improved bound for the stepping-up lemma", Discrete Applied Mathematics (to appear).

[25] И. Д. Шкредов, "Теорема Семереди и задачи об арифметических прогрессиях", УМН, 61:6 (2006), 111-179.

[26] И. Д. Шкредов, "Анализ Фурье в комбинаторной теории чисел", УМН, 65:3 (2010), 88-145.

[27| Е. W. Miller, "On a property of family of sets", Comptes Rendus Varsovie, 30 (1937), 31-38.

[28] C. Berge, Graphes et hypergraphes, Dunod, Paris, 1970.

[29] С. Berge, Hypergraphs, Combinatorics of finite sets, North-Holland Publishing, Amsterdam, 1989.

[30 [31

[32

[33

[34

[35 [3G [37 [38 [39 [40 [41

[42 [43

[44 [45

[46 [47 [48

[49

[50

[51 [52 [53

[54

[55 [56

А. А. Зыков, "Гиперграфы", УМН, 29:6 (1974), 89-154.

P. Erdos, A. Hajnal, "On chromatic number of graphs and set-systems", Acta Mathcmatica of the Academy of Sciences, Hungary, 17:1-2 (1966), 61-99.

M. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completencss, W.H. Freeman and Company, 1979.

P. Erdos, A. Hajnal, "On a property of families of sets", Acta Mathematica of the Academy of Sciences, Hungary, 12:1-2 (1961), 87-123.

P. Erdos, L. Lovasz, "Problems and results on 3-chromatic hypergraphs and some related questions", Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, 10, North Holland, Amsterdam, 1973, 609-627.

L. Lu, L. Szekely, "Using Lovasz Local Lemma in the space of random injections", Electronic Journal of Combinatorics, 13 (2007), Research paper №63.

A. Hajnal, E. Szeineredi, "Proof of a conjecture of P. Erdos", Combinatorial Theory and its applications, North-Holland, London, 1970, 601-623.

M. Ajtai, J. Komlos, J. Pintz, J. Spencer, E. Szemeredi, "Extremal uncrowded hypergraphs", Journal of Combinatorial Theory A, 32:3 (1982), 321-335.

V. Rodl, "On a packing and covering problem", European Journal of Combinatorics, 6:1 (1985), 69-78.

P. Erdos, H. Hanani, "On a limit theorem in combinatorial analysis", Publ. Math. Debrecen, 10 (1963), 10-13.

J. II. Kim, "On Brook's theorem for sparse graphs", Combinatorics, Probability and Computing, 4 (1995), 97-132.

A. Johanssen, "Asymptotic choice number for triangle free graphs", DIMACS Technical Report 91-95, 1996.

A. Frieze, D. Mubayi, "Coloring simple hypergraphs", arXiv:0809.2979v2.

J. Beck, "On a combinatorial problem of P. Erdos and L. Lovasz", Discrete Mathematics, 17:2 (1977), 127-131.

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

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

П. Эрдеш, Дж. Спенсер, Вероятностные методы в комбинаторике, Мир, М., 1976.

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

W. М. Schmidt, "Ein kombinatorisches Problem von P. Erdos and A. Hajnal", Acta Mathematica of the Academy of Sciences, Hungary, 15 (1964), 373-374.

Л. Beck, "On 3-chromatic hypergraphs", Discrete Mathematics, 24:2 (1978), 127-137.

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

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

M. Herzog, J. Schonheim, "The Br property and chromatic numbers of generalized graphs", J. Combinatorial Theory, Series B, 12 (1972), 41-49.

P. Erdos, "Some old and new problems in various branches of combinatorics", Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium XXIII, Utilitas Mathematica, Winnipeg, 1979, 19-37.

A. V. Kostochka, "Color-Critical Graphs and Hypergraphs with Few Edges: A Survey", More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15, eds. E. Gyori, G. О. II. Katona, L. Lovasz, Springer, 2006, 175-198.

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

P. Frankl, V. Rodl, "Lower bounds for Turan's problem", Graphs and Combinatorics, 1 (1985), 213-216.

Г] A. F. Sidorenko, "What we know and what we do not know about Turan numbers", Graphs and Combinatorics, 11 (1995), 179-199.

3] A. V. Kostochka, "Coloring uniform hypergraphs with few colors", Random Structures and Algorithms, 24:1 (2004), 1-10.

}] A. Pluhar, "Greedy colorings for uniform hypergraphs", Random Structures and Algorithms, 35:2 (2009), 216-221.

]] L. Lovasz, Combinatorial problems and exercises, North-Holland, New York, 1979.

L] A. V. Kostochka, V. Rodl, "Constructions of sparse uniform hypergraphs with high chromatic number", Random Structures and Algorithms, 36:1 (2010), 46-56.

2] R. L. Brooks, "On colouring the nodes of a network", Proc. Cambridge Philos. Soc., 37 (1941), 194-197.

3] G. Szekeres, H. S. Wilf, "An inequality for the chromatic number of a graph", J. Combinatorial Theory, 4 (1968), 1-3.

1] Ф. Харари, Теория графов, КомКнига, M., 2006.

5] Т. Tao, V. Vu, Additive Combinatorics, Cambridge University Press, Cambridge, 2006.

3] A.V. Kostochka, M. Kumbhat, V. Rodl, "Coloring uniform hypergraphs with small edge degrees", Fete of Combinatorics and Computer Science, Bolyai Society Mathematical Studies, 20, Springer, 2010, 213-238.

J\ В. Г. Визинг, "Раскраска вершин графа в предписанные цвета", Методы дискретного анализа в теории кодов и схем: сборник научных трудов, 29, Институт математики СО АН СССР, Новосибирск, 1976, 3-10.

3) P. Erdos, A. L. Rubin, Н. Taylor, "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing (Areata, 1979, Congr. Numer.), 26, 1980, 125157.

)] P. Erdos, "Graph theory and probability", Canadian Mathematical Bullettin, 11 (1959), 34-38.

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

1] A. V. Kostochka, D. Mubayi, V. Rodl, P. Tetali, "On the chromatic number of set systems", Random Structures and Algorithms, 19:2 (2001), 87-98.

2] T. Bohman, A. Frieze, D. Mubayi, "Coloring H-free hypergraphs", Random Structures and Algorithms, 36:1 (2010), 11-25.

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

1] A. V. Kostochka, M. Kubmhat, "Coloring uniform hypergraphs with few edges", Random Structures and Algorithms, 35:3 (2009), 348-368.

5] J. Steiner, "Combinatorische Aufgabe", Journal fur die Reine und Angewandte Mathematik, 45 (1853), 181-182.

3] E. F. Assinus Jr., J. D. Key, "Steiner Systems", Designs and Their Codes, Cambridge University Press, 1994, 295-316.

7\ T. Beth, D. Jungnickel, H. Lenz, Design Theory, 2nd ed., Cambridge University Press, Cambridge, 1986.

3] K. Phelps, V. Rodl, "Steiner triple systems with minimum independence number", Ars Combinatoria, 21 (1986), 167-172.

)] V. Rodl, E. Sinajova, "Note on independent sets in Steiner systems", Random Structures and Algorithms, 5:1 (1994), 183-190.

]] P. Erdos, A. Renyi, "On the evolution of random graphs", Publications of the Mathematical Institute of of the Hungarian Academy of Sciences, 5:1-2 (1960), 17-61.

1] B. Bollobas, Random graphs, Cambridge University Press, Cambridge, 2001.

2] S. Jansen, T. Luczak, A. Rucinski, Random graphs, Wiley-Interscience, New York, 2000.

3] M. Karoiiski, T. Luczak, "Random hypergraphs", Combinatorics, Paul Erdos is eighty, Bolyai Society Mathematical Studies, 2, eds. D. Miklos, V.T. Sos, T. Szonyi, Springer, 1996, 283-293.

[84] Г. П. Гаврилов, А. А. Саноженко, Задачи и упраэ/сиения по дискретной математике, Физ-матлит, М., 2005.

G. A. Dirac, "The structure of Achromatic graphs", Fund. Math., 40 (1953), 42-55.

B. Descartes, "Solution to advanced problem N 4526", Amer. Math. Monthly, 61 (1954), 352.

A. А. Зыков, "О некоторых свойствах линейных комплексов", Математический сбортт, 24(66):2 (1949), 163-188.

J. Mycielski, "Sur le coloriadge des graphes", Colloq. Math., 3 (1955), 161-162.

J. B. Kelly, L. M. Kelly, "Path and circuits in critical graphs", Amer. J. Math., 76 (1954), 786-792.

L. Lovasz, "On chromatic number of finite set-systems", Acta Mathcmatica of the Academy of Sciences, Hungary, 19 (1968), 59-67.

B.Г. Визинг, "Некоторые нерешенные задачи в теории графов", Успехи математических наук, 23:6 (1968), 117-134.

A. В. Косточка, Н. П. Мазурова, "Неравенство в теории раскрасок графов", Методы дискретного анализа, 30 (1977), 23-29.

B. Bollobas, "Chromatic number, girth and maximal degree", Discrete Mathematics, 24 (1978), 311-314.

B. Bollobas, Random graphs, Academic Press, London, 1984.

В. А. Ташкинов, "О нижней границе для хроматического числа графов с заданными максимальной степенью вершин и обхватом", Сгьбирские электронные математические известия, 1 (2004), 99-109.

O.V. Borodin, A.V. Kostochka, "On an upper bound of a graph's chromatic number depending on the graph's degree and density", Journal od Combinatorial Theory, Series B, 23 (1977), 247-250.

P. Catlin, "A bound on the chromatic number of a graph", Discrete Mathematics, 22 (1978), 81-83.

J. Lawrence, "Covering the vertex set of a graph with subgraphs of smaller degree", Discrete Mathematics, 21 (1978), 61-68.

A. Frieze, D. Mubayi, "On the chromatic number of simple triangle-free trimple systems", Electronic Journal of Combinatorics, 15 (2008).

L. Lu, On a problem of Erdos and Lovdsz on coloring non-uniform hypergraphs www.math.sc.edu/ lu/papers/propertyB.pdf

A. V. Kostochka, "On a theorem by Erdos, Rubin and Taylor on choosability of complete bipartite graphs", Electronic Journal of Combinatorics, 9:1 (2002), research paper N9.

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

A. М. Райгородский, Системы общих представителей в комбинаторике и их приложения в геометрии, МЦНМО, М., 2009.

Z. Fiiredi, "Turan's type problems", Surveys in Combinatorics (Proc. of the 13th British Combin. Conference), London Math. Soc. Lecture Note Series, 166, eds. A.D. Keechvell, Cambridge Univ. Press, 1991, 253-300.

B. E. Тараканов, Комбинаторные задачи и (0,1) - матрицы, Наука, М., 1985.

А. Н. Ширяев, Вероятность, В 2-х кн. — 3-е изд., перераб. и доп., МЦНМО, М., 2004.

Л. Galambos, I. Simonelli, Bonferroni-type inequalities with applications, Springer-Verlag, Berlin, 1996.

F. Gecseg, B. Imreh, A. Pluhar, "On the existance of finite isomorphic complete systems of automata", J. of Automata, Languages and Combinatorics, 3:2 (1998), 77-84.

A. V. Kostochka, D. R. Woodall, "Density conditions for panchromatic colourings of hypergraphs", Combinatorica, 21 (2001), 515-541.

R. Yuster, "Equitable coloring of k-uniform hypergraphs", SIAM Journal on Discrete Mathematics, 16:4 (2003), 524-532.

Ph. Hall, "On the representations of subsets", J. London Math. Soc., 10 (1935), 26-30. O. Ope, Теория графов, 2-е изд., Наука, М., 1980.

[113] H. Kierstead, "On the choosability of complete multipartite graphs with size part 3", Discrete Mathematics, 211 (2000), 255-259.

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

[115] N. Gazit, M. Krivelevich, "On the asymptotic value of the choice number of complete multipartite graphs", Journal of Graph Theory, 52 (2006), 123-134.

[116] А.Я. Хинчин, Три жемчуэюииы теории чисел, УРСС, М., 2004.

[117] A.M. Райгородский, Вероятность и алгебра в комбинаторике, МЦНМО, М., 2008.

[118] В. А. Успенский, Лекции о вычислимых функциях, Фитматгиз, М., 1960.

[119] S. Shelah, "Primitive recursive bounds for van der Waerden numbers", Journal of American Mathematical Society, 1:3 (1988), 683-697.

[120] P. Erdôs, P. Turan, "On Some Sequences of Integers", J. London Math. Soc., 11 (1936), 261-264..

[121] K. F. Roth, "On certain sets of integers", J. London Math. Soc., 28 (1953), 104-109.

[122] E. Szemerédi, "Integer sets containing no arithmetic progressions", Acta Mathcmatica of the Academy of Sciences, Hungary, 56:1-2 (1990), 155-158.

[123] D.R. Heath-Brown, "Integer sets containing no arithmetic progressions", J. London Math. Soc. (2), 35:3 (1987), 385-394.

[124] J. Bourgain, "On triples in arithmetic progression", Geometric and Functional Analysis, 9:5 (1999), 968-984.

[125] Л. Bourgain, "Roth's theorem on progressions revisited", Journal d'Analyse Mathématique, 104:1 (2008), 155-192.

[126] T. Sanders, "On Roth's theorem on progressions", Annals of Mathematics, 174:1 (2011), 619636.

[127] E. Szemerédi, "On sets of integers containing no four elements in arithmetic progression", Acta Mathcmatica of the Academy of Sciences, Hungary, 20:1-2 (1969), 89-104.

[128] E. Szemerédi, "On sets of integers containing no k elements in arithmetic progression", Acta Arithmetica, 27 (1975), 199-245.

[129] H. Furstenberg, "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", Journal d'Analyse Mathématique, 31 (1977), 204-256.

[130] W. T. Gowers, "A new proof of Szemerédi theorem", Geometric and Functional Analysis, 11 (2001), 465-588.

[131] B. Green, T. Tao, "New bounds for Szemerédi's theorem, II: a new bound for r,i(iV)", Analytic Number Theory: essays in honour of Klaus Roth, eds. W. Chen et al, Cambridge University Press, 2009, 180-204.

[132] V. Chvâtal, "Some unknown van der Waerden numbers", Combinatorial structures and their applications, Gordon and Breech, New York, 1970, 31-33.

[133] R. S. Stevens, R. Shantarain, "Computer generated Van der Waerden partitions", Mathematics of Computation, 32 (1978), 635-636.

[134] M. D. Beeler, P. E. O'Neil, "Some new van der Waerden numbers", Discrete Mathematics, 28 (1979), 135-146.

[135] P. Herwig, M. Heule, P. van Lambalgen, H. van Maaren., "A new method to contruct lower bounds for van der Warden numbers", The Electronic Journal of Combinatorics, 14 (2007), 1-18.

[136] P. Erdôs, R. Rado, "Combinatorial theorems on classifications of subsets of given set", Proceedings of London Mathematical Society, 2 (1952), 417-439.

[137] L. Moser, "On a theorem of van der Waerden", Canadian Mathematical Bulletin, 3 (1960), 23-25.

[138] W. M. Schmidt, "Two combinatorial theorems on arithmetic progressions", Duke Mathematical Journal, 29:1 (1962), 129 140.

[139] E. Berlekamp, "A construction for partitions which avoide long arithmetic progressions", Canadian Mathematical Bulletin, 11 (1968), 409-414.

[140] Т. Brown. В. Landman, A. Robertson, "Bounds on some van der Waerdcn numbers", Journal of Combinatorial Theory, Series A, 115 (2008), 1304-1309.

[141] F. A. Behrend, "On sets of integers which contain no three terms in arithmetical progression", Proceedings of Nat. Acad. Sci. USA., 32 (1946), 331-332.

[142] R. A. Rankin, "Sets of integers containing not more than a given number of terms in arithmetic progression", Proc. Roy. Soc. Edinburgh Sect. A, 65:4 (1960/1961), 332-344.

[143] M. Elkin, "An Improved Construction of Progression-Free Sets", Israeli Journal of Mathematics, 184 (2011), 93-128.

[144] B. Green, J. Wolf, "A Note on Elkin's Improvement of Behrend's Construction", Additive Number Theory, D. Chudnovski, G. Chudnovski eds., Springer, 2010, 141-144.

[145] K. O'Bryant, "Sets of integers that do not contain long arithmetic progressions", Electronic Journal of Combinatorics, 18 (2011), research paper N59.

[146] R. L. Graham, "Recent developments in Ramsey theory", Proceedings of the International Congress of Mathematicians, 1-2, PWN, Warsaw, 1984, 1555-1567.

[147] P. Erdos, "Some of my favorite unsolved Problems", The Mathematics of Paid Erdos, 1, Springer, Berlin, 1997, 47-67.

[148] R. L. Graham, "Some of my favorite problems in Ramsey theory", Proceedings of the 'Intergers Conference 2005' in celebtration of the 70th Birthday of Ronald Graham, Walter de Gruyter, Berlin, 2007, 229-236.

[149] R. L. Graham, "Old and new problems and results in Ramsey theory", Horizon of combinatorics, Bolyai Society Mathematical Studies, 7, eds. E. Gyori, G. О. II. Katona, L. Lovasz, Springer, 2008, 105 118.

[150] T. Luczak, "On the equivalence of two basic models of random graphs", Random Graphs, eds. M. Karoriski, J. Jaworski, A. Ruciriski, Wiley, 1987, 151-158.

[151] B. Bollobas, A. Thoinason, "Thresholds functions", Combinatorica, 7 (1987), 35-38.

[152] P. Erdos, A. Renyi, "On random graphs I", Publ. Math. Debrecen, 6 (1959), 290-297.

[153] В. Ф. Колчин, Случайные графы, Физматлит, М., 2000.

[154] D. Achlioptas, Е. Friedgut, "A sharp threshold for ^-colorability", Random Structures and Algorithms, 14:1 (1999), 63-70.

[155] P. Flajolet, D. Knuth, B. Pittel, "The first cycles in an evolving graph", Discrete Mathematics, 75:1-3 (1989), 167-215.

[156] N. Alon, J. Spencer, "A note on coloring random fc-sets", Unpublished manuscript.

[157| E. Friedgut, "Necessary and sufficient conditions for sharp thresholds of graph properties", Journal of the American Mathematical Society, 12 (1999), 1017-1054.

[158] D. Achlioptas, J.H. Kim, M. Krivelevich, P. Tetali, "Two-colorings random hypergraphs", Random Structures and Algorithms, 20:2 (2002), 249-259.

[159] D. Achlioptas, C. Moore, "On the 2-colorability of random hypergraphs", Random, Springer, Berlin, 2002, 78-90.

[160] B. Bollobas, "The chromatic number of random graphs", Combinatorica, 8:1 (1988), 49-56.

[161] T. Luczak, "The chromatic number of random graphs", Combinatorica, 11:1 (1991), 45-54.

[162] E. Shamir, "Chromatic number of random hypergraphs and associated graphs", Adv. Comput. Res., 5 (1989), 127-142.

[163] M. Krivelevich, B. Sudakov, "The chromatic numbers of random hypergraphs", Random Structures and Algorithms, 12 (1998), 381-403.

Список работ автора по теме диссертации

[Ш01] А. М. Райгородский, Д. А. Шабанов, "Задача Эрдеша-Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы", Успехи математических наук, 66:5 (2011), 109-182.

[Ш02] Д. А. Шабанов, "О хроматическом числе конечных систем подмножеств", Математические заметки, 85:6 (2009), 951-954.

[ШОЗ] А. П. Розовская, Д. А. Шабанов, "О правильных раскрасках гиперграфов в предписанные цвета", Дискретная математика, 22:3 (2010), 94-109.

[Ш04] Д. А. Шабанов, "Об улучшении нижней оценки в комбинаторной задаче Эрдеша - Хайна-ла", Доклады Академии Наук, 426:2 (2009), 177-178.

[Ш05] Д. А. Шабанов, "О нижних оценках числа ребер гиперграфа из некоторых классов", Доклады Академии Наук, 434:1 (2010), 33-37.

[Ш06] D. A. Shabanov, "On r-chroinatic hypergraphs", Discrete Mathematics, 312:2 (2012), 441-458.

[Ш07] Д. А. Шабанов, "О нижних оценках в комбинаторной задаче Эрдеша - Ловаса", Доклады Академии Наук, 431:5 (2010), 602-604.

[Ш08] D. A. Shabanov, "Random coloring method in the combinatorial problem of Erdos and Lovasz", Random Structures and Algorithms, 40:2 (2012), 227-253.

[Ш09] Д. А. Шабанов, "Частичные системы Штейнера и случайные гиперграфы", Современные проблемы математики и механики, 7:1 (2011), 68-76.

[Ш10] Д. А. Шабанов, А. Б. Купавский, "Раскраски однородных гииерграфов с большим обхватом", Доклады Академии Наук, 443:4 (2012), 422-426.

[Ш11] D. A. Shabanov, "On coloring uniform hypergraphs without 3-cycles", Moscow Journal of Combinatorics and Number Theory, 1:2 (2011), 100-126.

[Ш12] Д. А. Шабанов, "Об одном обобщении задачи Эрдеша-Ловаса", Труды МФТИ, 4:1 (2012), 131-140.

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

[Ш14] Д. А. Шабанов, "О существовании полноцветных раскрасок для равномерных гиперграфов", Математический Сборник, 201:4 (2010), 137-160.

[Ш15] D. A. Shabanov, "On a generalization of Rubin's theorem", Journal of Graph Theory, 67:3 (2011), 226-234.

[Ш16] Д. А. Шабанов, "О нижней оценке функции Ван дер Вардена", Математические заметки, 87:6 (2010), 951-953.

[Ш17] Д. А. Шабанов, "Функция Ван дер Вардена и раскраски гиперграфов", Известия РАН. Серия математическая, 75:5 (2011), 195-224.