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

• Автор: Шабанов, Дмитрий Александрович
• Шифр специальности: 01.01.05
• Научная степень: Докторская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 314 с.

Содержание
Введение
Общая характеристика работы
Глава 1. Задача Эрдеша — Хайнала о раскрасках гиперграфов
§1.1 История задачи Эрдеша - Хайнала
§1.2 Новые оценки в задаче Эрдеша - Хайнала
§1.3 Доказательство первой оценки в задаче Эрдеша Хайнала . .
§1.4 Метод случайной перекраски в проблеме Эрдеша Хайнала . 30 §1.5 Доказательство второй оценки в задаче Эрдеша Хайнала . .
§1.6 Экстремальные задачи для максимальных реберных и вершинных степеней гиперграфа
§1.7 Доказательство нижней оценки максимальной степени ребра
в гиперграфах с большим обхватом
§1.8 Задача Эрдеша - Хайнала для предписанных раскрасок .... 51 §1.9 Доказательство нижней оценки в задаче Эрдеша-Хайнала для
предписанных раскрасок
Глава 2. Задача Эрдеша — Ловаса о раскрасках простых гиперграфов
§2.1 История задачи Эрдеша - Ловаса
§2.2 Новые результаты в задаче Эрдеша - Ловаса
§2.3 Частичные системы Штейнера и ^-простые гиперграфы
§2.4 Доказательство оценок величины т*(л, г, I)
§2.5 Оценки максимальной степени вершины в простых гиперграфах с большим хроматическим числом
§2.6 Доказательства нижних оценок в задаче Эрдеша - Ловаса ... 88 §2.7 Доказательство нижней оценки максимальной степени ребра
в простых гиперграфах с большим хроматическим числом ... 91 §2.8 Оценки максимальной реберной степени в (п, I)-системах с большим хроматическим числом

§2.9 Доказательство нижней оценки максимальной степени ребра
в (тгД)-системах с большим хроматическим числом
Глава 3. Раскраски гиперграфов с большим обхватом
§3.1 Оценки максимальной степени вершины в графах и гппергра-
фах с большим хроматическим числом и большим обхватом . . 137 §3.2 Доказательство оценки максимальной степени ребра в гипер-графах с большими хроматическим числом и обхватом больше

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

§3.4 Задача типа Эрдеша - Хайнала для гиперграфов с большим
обхватом
§3.5 Раскраски неоднородных гиперграфов с большим обхватом . . 186 §3.6 Доказательство теоремы о неоднородных гиперграфах
Глава 4. Задачи о полноцветных раскрасках гиперграфов и их
приложения
§4.1 Задача Косточки о полноцветных раскрасках гиперграфов
§4.2 Доказательство нижней оценки величины р(п,г)
§4.3 Доказательства верхних оценок величины р(п, г)
§4.4 Достаточное условие существования полноцветных раскрасок . 221 §4.5 Асимптотика предписанного хроматического числа полных многодольных графов
Глава 5. Функция Ван дер Вардена и раскраски гиперграфов
§5.1 Теорема Ван дер Вардена об арифметических прогрессиях . . 231 §5.2 Доказательство нижней оценки функции Ван дер Вардена . . 241 §5.3 Доказательство второй оценки функции Ван дер Вардена
Глава 6. Раскраски случайных гиперграфов
§6.1 Общие сведения из теории случайных подмножеств
§6.2 Пороговая вероятность 2-раскрашиваемости случайного гиперграфа
§6.3 Пороговая вероятность г-раскрашиваемости случайного гипер-
графа
§6.4 Новые нижние оценки пороговой вероятности г-раскрашпва-
емостп случайного гиперграфа
Список цитированной литературы
Список работ автора по теме диссертации
Введение
Настоящая диссертация посвящена исследованию классических задач о раскрасках гиперграфов, находящихся на стыке экстремальной и вероятностной комбинаторики, теории Рамсея, аддитивной комбинаторики и теории графов.
Приведем ряд основных определений. Гиперграфом Н называется пара множеств Н = (У,Е), где V = V(Н) — некоторое (как правило, конечное) множество, называемое множеством вершин гиперграфа, а Е = Е(Н) — произвольная совокупность подмножеств множества V, называемых ребрами гиперграфа. Гиперграф является п-одиородным, если каждое его ребро содержит ровно п вершин. Ясно, что 2-однородный гиперграф — это обыкновенный граф (без петель, кратных ребер и ориентации).
Экстремальные задачи о раскрасках гиперграфов впервые возникли в классических работах 20-30-х годах XX века, положивших начало теории Рамсея. Формально говоря, теория Рамсея — это не теория в общепринятом смысле, а набор различных результатов из анализа, геометрии, комбинаторики, теории чисел и т.д., которые объединены общей философией их восприятия. Основной принцип теории Рамсея можно сформулировать следующим образом:
при любом разбиении па небольшое число частей очень большой регулярной структуры обязательно найдется часть этого разбиения, содерэюащая достаточно большую регулярную подструктуру.
Задачи рамсеевского типа берут свое начало в комбинаторике с теоремы Рамсея 1930 года (см. [1]), в теории чисел — с теоремы Ван дер Вардена 1927 года (см. (2)), в геометрии — с проблем Эрдеша - Секереша, поставленных в 1935 году (см. [3]). Историю задач типа Эрдеша - Секереша, а также последние достижения в этой области можно найти, например, в следующих книгах и обзорах: [4]—[8]. Первые же две теоремы очень тесно связаны с раскрасками гиперграфов и, но сути, стимулировали развитие теории раскрасок гпперграфов.
Теорема Рамсея является глубоким обобщением классического принципа Дирихле, а потому лежит на стыке комбинаторики и логики. Сформулируем данный результат (доказательство которого можно найти, например, в книге [9]) в его максимальной общности. Пусть 5 — множество из п элементов,

раскраске £ и в течение процедуры перекраски ни одна из вершин е не сменила цвет. Событие В(е) означает, что ребро е было одноцветным, например, некоторого цвета и в финальной раскраске , а в основной раскраске £ оно было покрашено не более, чем в два цвета: и и некоторый другой цвет а. Единственная оставшаяся нерассмотренной возможность того, как е могло оказаться полностью покрашенным в цвет и в раскраске состоит в том, что изначально в основной раскраске £ ребро є содержало вершины по крайней мере еще двух цветов, помимо и. Это событие мы обозначили через С(е). В силу определений (1.22), (1.23) и (1.24) получаем соотношение
Т=и (Л(е)иВДиС(е)). (1.25)

Далее, мы проанализируем эти три события по-отделыюсти.
1.4.4 Первое событие
Предположим, что произошло событие Л(е). Пусть ребро е покрашено полностью в цвет и в основной раскраске £. Из того, что ф = ф = и для всех З Є е, вытекают (см (1.21)) равенства = ■ • ■ = С]°^ — Сі
также для всехЄ е. Если же, например, ^к> ф и, то из (1.21) следует, что С^+1) = ф ф и, и, тем самым, не выполнено событие Пф, к + 1). А значит, вершина j не может иметь цвет и в финальной раскраске (Д!■ Мы получили противоречие с событием Л(е).
Равенства же = • • • = С]°^ = Сі = и Для всех І Є є имеют место
тогда и только тогда, когда г/^к> Є {0, и} для всех j Є є и всех к = 1,..., 5. Таким образом,
лм = ип (&=«} п
и=1ІЄ е
В силу того, что случайные величины ф, независимы в совокупности, вероятность' события Л(е) легко находится:
Р(Л(е)) = 5^X1 (р & = ■ П Р (ч?1 € {0,«})
и=1jЄe к=
= г1-п(1 - (г - 1)р)"8 = г1~п{1 - д)п°. (1.27)
Здесь мы использовали обозначение д = (г — 1 )р.
ПШД є {о,«}}
(1.26)