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

Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. A.A. Харкевича Российской академии наук

На правах рукописи УДК 519.212.2, 519.112.7

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

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

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

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

005049841

Москва — 2012

г 1 фев т

005049841

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

Официальные оппоненты: доктор физико-математических наук, профессор, Кабатянский Григорий Анатольевич, главный научный сотрудник Института проблем передачи информации им. A.A. Харкевича РАН

доктор физико-математических наук, профессор, Павлов Юрий Леонидович, заведующий лабораторией Института прикладных математических исследований Карельского научного центра РАН

доктор физико-математических наук, профессор, Шкредов Илья Дмитриевич, ведущий научный сотрудник Математического института им. В.А. Стеклова РАН

Ведущая организация: Хабаровское отделение

Института прикладной математики Дальневосточного отделения РАН

Защита диссертации состоится 26 марта 2013 года в 16 часов на заседании диссертационного совета Д 002.077.03 при Федеральном государственном бюджетном учреждении науки Институте проблем передачи информации им. A.A. Харкевича РАН, расположенном по адресу: 127994, Москва, ГСП-4, Большой Каретный переулок, 19, стр.1.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации им. A.A. Харкевича РАН.

s~

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

Ученый секретарь диссертационного совета Д 002.077.03 при ИППИ РАН, кандидат физико-математических наук,

А.Н. Соболевский

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

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

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

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

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

Экстремальные задачи о раскрасках гиперграфов впервые возникли в классических работах 20-30-х годов XX века, положивших начало теории Рамсея. Проблемы рамсеевского типа берут свое начало в комбинаторике с теоремы Рамсея1 1930 года, а в теории чисел — с теоремы Ван дер Вардена2 1927 года. Обе эти теоремы очень тесно связаны с раскрасками гиперграфов и, по сути, стимулировали само развитие теории раскрасок гиперграфов.

Теорема Рамсея является глубоким обобщением классического принципа Дирихле, а потому лежит на стыке комбинаторики и логики. Сформулируем данный результат в его максимальной общности. Пусть S — множество из п элементов, обозначим через Pk{S) — множество всех fc-элементных подмножеств S. Пусть также даны натуральные числа í ^ 2 и si,..., st с условием Si ^ к для любого i = 1,..., t.

Теорема. (Ф. Рамсей, 1930) Существует такое минимальное натуральное число R(s i,... ,st", к), что если n ^ R (si,..., st; к), то при любом упо-

'F.P. Ramsey, On a problem of formal logic, Proc. of London Math. Society Ser. 2, 30 (1930), 264-286.

2B.L. van der Waerden, "Beweis einer Baudetsclien Vermutung", Nieuw Archief voor Wiskunde, 15 (1927), 212-216.

рядоченном t-разбиении Ai U ... U At множества Pk(S) найдется г и s,-подмножество множества S, все к-подмножества которого содержатся

в А{.

Величину R(su..., st; к) из теоремы Рамсея принято называть числом Рамсея. Исследование асимптотического поведения числа Рамсея является одной из центральных задач экстремальной комбинаторики. Ее непосредственному изучению посвящены работы таких классиков комбинаторной математики, как П. Эрдеш, Дж. Секереш, Р. Радо, А. Хайнал, Е. Семереди, Дж. Спенсер, В. Рёдль, а также таких известных математиков, как Я. Ком-лош, М. Айтаи, П. Франкл, Р. Уилсон, А. Вигдерсон, Э. Томасон, Дж. Ким, Д. Конлон, Дж. Фокс, Б. Судаков, Т. Боман, П. Киваш и др. Подробнее с результатами вышеперечисленных авторов можно ознакомиться, например, в обзоре3.

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

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

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

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

3В. Sudakov, "Recent developments in extremal combinatorics: Ramsey and Turan type problems", Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010, 2579-2606.

4И.Д. Шкрсдов, "Теорема Сомсроди и задачи об арифметических прогрессиях", УМЯ, 61:6 (2006), 111179.

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

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

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

Используемое сегодня понятие правильной раскраски гиперграфа было предложено П. Эрдешем и А. Хайналом6 в 1966 году. Согласно их определению раскраска множества вершип V гиперграфа H = (V, Е) называется правильной, если в этой раскраске все ребра из Е не являются одноцветными (т.е. содержат вершины разных цветов). Хроматическим числом гиперграфа H называется минимальное число цветов, требуемое для правильной раскраски вершин этого гиперграфа. Мы будем обозначать хроматическое число гиперграфа H через х{Щ- Если х{Н) < г, т.е. для гиперграфа H существует правильная раскраска вершин в г цветов, то говорят, что H является r-раскрашиваемым. Подобное определение хроматического числа очень хорошо сочетается с другими характеристиками гиперграфа (число независимости, максимальная степень вершины и т.п.), позволяя сохранить ту же самую взаимосвязь между ними, что и в обычных графах. Как и для графов, с точки зрения вычислений проблема r-раскрашиваемости гиперграфа в общем случае является NP-полной, а проблема нахождения хроматического числа — NP-трудной7. В связи с этим естественным образом возник вопрос

6Р. Erdôs, A. Hajnal, "On chromatic number of graphs and set-systems", Acta Mathematica of the Academy of Sciences, Hungary, 17:1-2 (10GG), 01-09.

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

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

Одной из первых возникших на этом пути задач явилась экстремальная задача Эрдеша и Хайнала о раскрасках гиперграфов, впервые поставленная ими в 1961 году8. Проблема состоит в том, чтобы отыскать величину т(п,г), равную минимально возможному количеству ребер гиперграфа в классе п-однородных гиперграфов, не являющихся г-раскрашиваемыми. Несмотря на простоту формулировки, задача о нахождении величины т{п, г) до сих пор не решена при п ^ 3 (в том время, как в случае графов, п = 2, она представляет собой несложное упражнение для школьников). Проблема Эрдеша - Хайнала — это, несомненно, центральная задача теории раскрасок гиперграфов. В настоящее время существует огромное количество ее обобщений для различных классов гиперграфов и видов раскрасок, по сути можно говорить о целом направлении в экстремальной комбинаторике, связанном с этой задачей. В общем виде задачу типа Эрдеша - Хайнала можно сформулировать следующим образом: найти минимально возможное значение некоторой характеристики гиперграфа (например, число ребер или максимальная степень вершины) в классе однородных гиперграфов, не допускающих раскрасок специального вида (например, правильных r-раскрасок, полноцветных г-раскрасок или предписанных раскрасок), а также, возможно, обладающих некоторыми дополнительными свойствами (например, обхват больше s). Из задач подобного рода особый интерес представляет изучение нижних оценок максимальной степени вершины гиперграфа с большим хроматическим числом и большим обхватом. Такие результаты дают достаточные условия г-раскрашиваемости разреженных гиперграфов, а потому находят обширные применения в теории Рамсея.

Экстремальным задачам типа Эрдеша - Хайнала о раскрасках графов и гиперграфов посвящены работы таких классиков комбинаторики, как П. Эр-деш, А. Хайнал, Н. Алон, Дж. Спенсер, Л. Ловас, П. Сеймур, Й. Бек, В. Рёдль, Б. Боллобаш, а также таких известных математиков, как А. В. Косточка, Д. Мубаи, А. Фриз, П. Тетали, 3. Сабо, Дж. Ким, Дж. Радхакришнан, А. Сринивасан, А. Плухар и многих других. Подробнее о результатах перечисленных авторов можно прочитать, например, в обзорах 9, 10. Результаты относительно задачи Эрдеша - Хайнала и ее обобщений нашли применение в теории Рамсея, теории графов, аддитивной комбинаторике, теории случай-

SP. Erdos, A. Hajual, "On a property of families of sets", Acta Ma.thema.tica of the Academy of Sciences, Hungary, 12:1-2 (1961), 87-123.

9A.V. Kostochka, "Color-Critical Graphs and Hypergraplis with Few Edges: A Survey", More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15, eds. E. Györi, G. О. H. Katona, L. Loväsz, Springer, 20UG, 175-198.

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

ных гиперграфов.

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

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

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

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

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

Второй замечательной вероятностной техникой, получившей качественное развитие в задачах о раскрасках гиперграфов, является "полуслучайный" метод (в зарубежной литературе принято название semi-random или nibble метод). Впервые основные идеи этого метода появились в работе М. Айтаи, Я. Комлоша, Дж. Пинца, Дж. Спенсера и Е. Семереди12 1972 года для получения нижней оценки числа независимости однородного гиперграфа с ограниченной максимальной степенью вершины и большим обхватом. Их вероятностная техника была существенно доработана В. Рёдлем13 в 1985 году для доказательства знаменитой гипотезы Эрдеша - Ханани14 о минимальных (п, к, ^-конфигурациях. Данная область комбинаторной математики тесно связана с асимптотическими вопросами теории кодирования, с проблемами о, так называемых, упаковках и покрытиях. В теории же раскрасок графов и гиперграфов полуслучайный метод получил качественное развитие. Так, например, в 1995-96 годах с его помощью А. Йоханссеном15 и Дж. Кимом16 были получены асимптотически неулучшаемые оценки хроматического числа графов с большим обхватом в зависимости от максимальной степени вершины. Кроме того, сочетая данный метод с применением Локальной леммы и других вероятностных инструментов, Д. Мубаи и А. Фриз17 получили в 2008 году гораздо более сильный результат, нежели Айтаи, Комлош и их соавторы, о верхней оценке хроматического числа простого гиперграфа с ограниченной максимальной степенью вершины.

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

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

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

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

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

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

17A. Frieze, D. Mubayi, Coloring simple hypergraphs, arxiv:0809.2979v2

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

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

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

Цель работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Разработана модификация метода случайной перекраски Бека - Спенсера для случая гиперграфов с обхватом больше трех. С ее помощью

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

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

7. Получено новое достаточное условие г-раскрашиваемости неоднородного

гиперграфа Н = (V, Е) с обхватом больше трех в терминах ограничения

на функцию /Г(Я) = ^ г1_'в1.

ее Е

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

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

10. На основе разработанных улучшений метода случайной перекраски доказаны новые нижние асимптотические оценки функции Ван дер Вар-дена.

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

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

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

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

Диссертация носит теоретический характер. Результаты и методы работы могут быть полезны в исследованиях задач экстремальной и вероятностной комбинаторики, теории графов и теории Рамсея, связанных с раскрасками гиперграфов. Они могут быть интересны специалистам, работающим в МГУ имени М.В.Ломоносова, МИРАН им. В.А. Стеклова, ИППИ РАН им. 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. Семинар «Дискретный анализ», факультет ВМиК МГУ имени М.В.Ломоносова, руководитель — профессор 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, февраль 2012).

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

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

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

19. Семинар в Массачусетском Технологическом Институте, г. Бостон, США, руководитель — профессор Д. Гамарник (март 2012).

20. Семинар «Combinatorics Seminar», Технологический Институт Джорджии, г. Атланта, США, руководитель — профессор П. Тетали (ноябрь 2012).

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

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, Орсе, Франция, 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 г.

10. 4th Polish Combinatorial Conference, Бедлево, Польша, 17 сентября - 21 сентября 2012 г.

Публикации.

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

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

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

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

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

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

Первая глава диссертации состоит из девяти параграфов и посвящена классической задаче Эрдеша - Хайнала о раскрасках гиперграфов и ряду смежных проблем. В 1961 году П. Эрдеш и А. Хайнал8 сформулировали проблему о нахождении величины т(п,г), равной минимально возможному числу ребер гиперграфа в классе п-однородных гиперграфов с хроматическим числом больше г. Формально определение т(п,г) можно записать следующим образом:

тп(п, г) = min {|£(//)| : Н — n-однородный гиперграф, х{Н) > г} •

В параграфе 1.1 обсуждается история задачи Эрдеша - Хайнала о величине m(n, г). В параграфе 1.2 формулируются две новые нижние оценки величины тп(п,г) и приводится сравнение полученных результатов с ранее известными. Эти результаты сформулированы в следующих двух теоремах.

Теорема 1. Для любых п ^ 3, г ^ 2 выполняется неравенство

т(п, г) ^ (V е-пгЬт) (п _ г"+2/г. (!)

V ' е\/27г

Теорема 2. Для любых п ^ 3, г ^ 3 выполняется неравенство

m{n,r)>^nll2rn-1. (2)

Нижние оценки (1) и (2) величины тп(п, г) в совокупности улучшают предыдущие результаты П. Эрдеша19, Н. Алона20, A.B. Косточки21 и А. Плухара22 в широкой асимптотической области значений параметров виг:

г = 3 и г ^ у/1/81п((1птг)/2).

Параграф 1.3 посвящен доказательству теоремы 1. Оно использует критерий Плухара r-раскрашиваемости произвольного гиперграфа в терминах существования нумерации его вершин специального вида, а также простой вероятностный метод.

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

В параграфе 1.5 с помощью анализа случайной раскраски из §1.4 обосновывается теорема 2 о нижней оценке величины m(n,r).

Параграф 1.6 посвящен экстремальным задачам типа Эрдеша - Хайнала для максимальных реберных и вершинных степеней гиперграфа. Пусть Я — гиперграф, a v — его некоторая вершина. Степенью вершины v в гиперграфе Я называется количество ребер Я, которые содержат эту вершину. Степенью оке ребра / в гиперграфе Я называется количество других ребер

19Р. Erdös, "On a combinatorial problem, I", Nordisk Mat. Tidskrift, 11 (19G3), 5-10.

20N. Alou, "Hypergraplis with liigli chromatic number", Graphs and Combinatorics, 1 (1985), 387-389.

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

22A. Pluhär, "Greedy colorings for uniform hypergraphs", Random Structures and Algorithms, 35:2 (2009), 216-221.

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

Н, которые имеют непустое пересечение с /. Максимальная степень вершины в гиперграфе Н обозначается через А (Я), а максимальная степень ребра — через Ае(Н).

По аналогии с задачей Эрдеша - Хайнала рассматриваются экстремальные величины А(п, г) и Ае(п, г), равные минимально возмоэюному значению А(Н) и Ае(Н), соответственно, где Н — п-однородный гиперграф с хроматическим числом больше г. Другими словами,

A(n,r) = min{A(#) : Н — n-однородный, х(Ю > г} ,

Ае(п, г) = min {Ае(Н) : Н — п-однородный, х(Н) > г} . Основным результатом §1.6 является новая нижняя оценка величины Ае(п, г). Теорема 3. Для любых п ^ 3 и г ^ 3 выполняется неравенство

A e(n,r)>in1/V-1. (3)

Оценка (3) улучшает предыдущие результаты Эрдеша и Ловаса11 и Косточки, М. Кумбхата, В. Рёдля24 в широкой асимптотической области значений параметров п и г :

г = 3 и г = Г2 ^Vln In nj .

Следствием из теоремы 3 является новая нижняя оценка величины Д(п, г). Следствие 1. Для любых п^Змг^З выполняется неравенство

A(n,r) > \п-1'2гп-\ (4)

8

В параграфе 1.7 также с помощью вероятностной конструкции из §1.4 доказывается теорема 3.

Параграф 1.8 посвящен обобщению классической задачи Эрдеша - Хайнала для предписанных раскрасок. Пусть Н = (V, Е) — гиперграф с множеством вершин V и множеством ребер 2?, а С — некоторое множество, элементы которого называются цветами. Вершинным предписанием А называется отображение, которое каждой вершине v ставит в соответствие некоторое (непустое) подмножество A{v) С С. Если И(г>)| = г для любой вершины V € V, то говорят, что мощность предписания А равна г.

Раскраской / вершин графа G, соответствующей предписанию А, называется такое отображение / : V —> С, что f(v) € A(v) для любого v € V. При

24A.V. Kostochka, М. Kumbhat, V. Rödl, "Coloring uniform hypergraphs with small edge degrees", Fete of Combinatorics and Computer Science, Bolyai Society Mathematical Studies, 20, Springer, 2010, 213-238.

этом говорят, что каждая вершина v окрашена в цвет f(v). Гиперграф называется предписанно г-раскрашиваемым, если для любого множества цветов С и любого вершинного предписания А мощности г найдется правильная раскраска, соответствующая данному предписанию. Предписанным хроматическим числом гиперграфа Я называется такое минимальное натуральное число г, что Я является предписанно r-раскрашиваемым. Предписанное хроматическое число гиперграфа Я обозначается через ch(H).

Изучение предписанных хроматических чисел графов и гиперграфов было инициировано работами В.Г. Визинга25, а также Эрдеша, A.JI. Рубина и Г. Тейлора26.

В работах А. В. Косточки9'21 было сформулировано следующее обобщение задачи Эрдеша - Хайнала для предписанных раскрасок: отыскать величину miist{n, г), равную минимально возможному количеству ребер гиперграфа в классе п-однородных гиперграфов, предписанное хроматическое число каждого из которых превышает г. Формально данное определение можно записать следующим образом:

тп1ш(п,г) = min {\Е(Н)\ : Я — n-однородный гиперграф, ch(II) > г} .

В силу очевидного неравенства ch(H) > х(Щ для произвольного гиперграфа Я, соотношение между величинами m;!St(n> г) и т(п> г) будет обратным:

miist(n,r) ^ т(п,г).

Основным результатом §1.8 является новая нижняя оценка m¡¿s¿(n, г), совпадающая с оценкой (2) для т(п, г).

Теорема 4. Для любых п ^ 3 и г ^ 3 выполняется неравенство

miist(n,r) ^ in1/2r"_1. (5)

Оценка (5) асимптотически улучшает все ранее известные результаты при всех г ^ 3.

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

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

26Р. Erdös, A.L. Rubin, Н. Taylor, "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, 26, 1980, 125-157.

Вторая глава диссертации состоит из девяти параграфов и посвящена классической задаче Эрдеша - Ловаса о раскрасках простых гиперграфов, а также ряду ее обобщений. Одно из первых обобщений задачи Эрдеша - Хай-нала возникло в знаменитой работе Эрдеша и Ловаса11 в 1973 году. Авторы предложили рассмотреть вопрос о нахождении минимального числа ребер n-однородпого гиперграфа с хроматическим числом больше г на множестве простых гиперграфов. Напомним, что гиперграф называется простым, если любые два различных ребра этого гиперграфа имеют не более одной общей вершины. По аналогии с т(п,г) через m*(n, г) Эрдеш и Ловас обозначили экстремальную величину

m*(n,r) = min {\Е(Н)\ : Н — n-однородный простой гиперграф, х(Н) > г} .

В параграфе 2.1 обсуждается история задачи Эрдеша - Ловаса о величине т*(п,г), приводятся ее ранее известные асимптотические верхние и нижние оценки.

Параграф 2.2 посвящен новым результатам в задаче Эрдеша - Ловаса, а также их сравнению с ранее известными результатами. В диссертации получено три новых нижних асимптотических оценок величины m*(n, г), первая из которых сформулирована в теореме 5.

Теорема 5. Существует такое натуральное число по, что для всех п > по и всех г ^ 2, удовлетворяющих соотношению г ^ п1/0, выполнено неравенство

т*(п + l,r) ^ ^г2п-2п-6/', (6)

где t = t(n + l,r) =

(Inn lnr>

mini;"';, 21n((4/3)lnn))

Сформулируем следствие данной теоремы, проясняющее порядок роста правой части оценки (6) при различных значениях г.

Следствие 2. Имеют место две ситуации.

1) Существует такое натуральное число щ, что для всех п^ щ и для всех г, удовлетворяющих неравенству г < у 1п2(п — 1), выполнено

т*(п, г) > і г2п~\п - 1)~в[>/».

2) Существует такое натуральное число щ, что для всех п ^ по и для всех г, удовлетворяющих соотношениям ^1п2(п — 1) ^ г < (п — І)1/9, выполнено _ ,

Следующие два результата §2.2 дают, в отличие от теоремы 5, нижние оценки т*(п,г) в отсутствии верхних ограничений для параметра г.

Теорема 6. Для всех п ^ 3, г ^ 3 выполняется неравенство

т,(п'г)^гП"2/3 (7)

Теорема 7. Для всех п ^ 3, г ^ 6 выполняется неравенство

"•<*'> И)- ®

Полученные в диссертации оценки (6), (7) и (8) величины m*(n, г) в совокупности улучшают ранее известные результаты Эрдеша и Ловаса11, Сабо27, Косточки, Мубаи, Рёдля и Тетали28, Косточки и М. Кумбхата29 в широкой асимптотической области значений параметров п и г:

In г = П((2,5)п).

Параграф 2.3 посвящен обобщениям проблемы Эрдеша - Ловаса для (п, I)-систем. Свойство простоты гиперграфа можно переформулировать следующим образом: гиперграф является простым, если любые две вершины этого гиперграфа содержатся (как подмножество) не более нем в одном ребре. Подобное свойство гиперграфов может быть обобщено естественным образом для Z-подмножеств множества вершин гиперграфа. Назовем (п,1)-системой n-однородный гиперграф, каждые I вершин которого содержатся (как подмножество) не более чем в одном ребре гиперграфа. В мировой литературе (п, /)-системы также принято называть частичными системами Штейнера.

В работе Косточки, Мубаи, Рёдля и Тетали28 2001 года была поставлена задача об отыскании величины т*(п,г,1), равной минимально возможному числу ребер в (п, 1)-системе с хроматическим числом, большим г. Ясно, что в частном случае I = 2 данная задача совпадает с задачей Эрдеша - Ловаса о простых гиперграфах, а при I — п она превращается в классическую задачу Эрдеша - Хайнала. В параграфе приводятся ранее известные асимптотические оценки величины т*(тг,г,1) и осуществляется их сравнение.

Основными результатами §2.3 являются новые оценки величины т*(п, г, I). Первая из них выполнена для всех I ^ 3.

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

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

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

Теорема 8. Существует такая полоэюительная константа С, что для любых выполняется неравенство

m*(n,r,l) ^Cn-W-V (г""1 Inr)l/{'-2). (9)

Если, к тому оюе, г ^ п, то

rn*(n, г, ZK с ^ j (г"-1 In r)w~2). (10)

Новые результаты (9) и (10) улучшают ранее известные оценки Косточки, Мубаи, Рёдля и Тетали28, Косточки и Кумбхата29, Т. Бомана, А. Фриза и Д. Мубаи30, Косточки и Рёдля31 в асимптотической области:

71 In Т

--— = o(l Inn), где I = l(n) -> +00 при n —¥ -boo.

Кроме того, в диссертации получена новая нижняя оценка для m"(n,r,l), которая улучшает один из результатов работы Косточки, Мубаи, Рёдля и Тетали28.

Теорема 9. Для любых п > I ^ 2 и четных г ^ 6 выполняется неравенство

,ч itn-lh-A1'1'-1* , 3/2 /Г\(»-1)'/(1-1)

(2)

Параграф 2.4 посвящен доказательствам теорем 8 и 9 об оценках величины тп*(п,г,1). Доказательство теоремы 8 опирается на рассмотрение биномиальной модели случайного гиперграфа, а основой доказательства теоремы 9 является комбинаторная лемма, проясняющая тесную связь величины т*{п,г,1) с экстремальной величиной А(п,г), относительно которой результаты были получены в первой главе, §1.6.

В параграфе 2.5 изучается задача типа Эрдеша - Ловаса для максимальной степени вершины. Рассматривается величина Д*{п,г), которая является аналогом Д(п, г) для класса простых гиперграфов:

Д*(п, г) = гшп{Д(#) : Н — n-однородный простой, х{Щ > f},

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

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

31 A.V. Kostoclika, V. Rödl, "Constructions od sparse uniform hypergraphs with high chromatic number", Random Structures and Algorithms, 36:1 (2010), 46-56.

Исследование величины Д*(п,г) также началось с работы Эрдеша и Лова-са11 в связи с их классической задачей об изучении т*(п,г). В диссертации получены две новые нижние оценки Д*(п, г). Первая из них сформулирована в теореме 10.

Теорема 10. Существует такое натуральное число по, что для всех п > по и всех г ^ 2, удовлетворяющих соотношению г < п1/9, выполнено неравенство

Д>,г) (11)

где í = £(п, г)

(1пп 1пг>

тт...... .

21п((4/3) 1пп)

Вторая же оценка дает универсальную (выполненную для всех г ^ 3) нетривиальную нижнюю оценку для Д*(п,г).

Теорема 11. Для любых п ^ 3, г ^ 3 выполняется неравенство

А*(п,г)>±г^п-^. (12)

Оценка (12) является первой нетривиальной (т.е. не вытекающей из неравенства Д*(п, г) ^ Д(п,г)) нижней оценкой Д*(п,г), которая выполнена при всех достаточно больших значениях числа цветов г.

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

Теорема 12. Пусть п ^ 3 и г ^ 3 — натуральные числа. Если п-однород-ный простой гиперграф Н удовлетворяет условию

Ае(Н) ^ ¿^п2'3,

то х{Н) ^ г-

Параграф 2.6 посвящен выводу нижних оценок (6), (7) и (8) в задаче Эрдеша - Ловаса о величине т*(п,г). Доказательства теорем основаны на комбинаторных леммах о связи между т*(тг,г) и Д*(п,г), а также использовании нижних оценок (11) и (12) для Д*(п, г).

Доказательство теоремы 12 приведено в параграфе 2.7. Оно основано на применении метода случайной перекраски. Как и в параграфе §1.4, вероятностная конструкция §2.7 использует идею многократного перекрашивания. Но в отличие от класса всех п-однородных гиперграфов для подкласса простых п-однородных гиперграфов особое внимание в случайном процессе

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

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

Теорема 13. Существует такое натуральное число щ, что для всех п > по, всех удовлетворяющих соотношению

По сравнению с предыдущей работой Косточки и Кумбхата полученная в диссертации теорема 13 существенно расширяет область значений параметров (см. (13)), в которых обосновывается оценка, а также улучшает и само верхнее ограничение (см. (14)) на Ае(Н). Простым следствием теоремы 13 является теорема 10 о нижней оценке величины А*(п,г). В свою очередь, сама теорема 13 является частным случаем следующей многопараметрического утверждения, дающего достаточное условие г-раскрашиваемости (п, I)-системы с ограниченной максимальной степенью ребра.

Теорема 14. Пусть заданы натуральные числа п ^ 3, г ^ 2, /і ^ 1, а также положительные числа к, с и а. Введем обозначения

Пусть Н = (V, Е) — (п,к + 1 )-система с максимальной степенью ребра Де(Я) = <1, причем выполнено неравенство

(13)

(14)

й ^ гп'1п1-к'1 - 1.

Если, кроме того, выполняются соотношения

2'

nlnn 13

2" +(рс]+1)з

то гиперграф Н является г-раскрашиваемым.

В конце §2.8 дается вывод теоремы 13 из теоремы 14.

Последний параграф второй главы, параграф 2.9, полностью посвящен доказательству теоремы 14. Доказательство опирается на модификацию метода случайной перекраски. При этом конструкция случайной раскраски для (п, ¿)-систем не использует идею многократного перекрашивания из §1.4, но как и конструкция для простых гиперграфов из §2.7, основывается на особом рассмотрении "почти одноцветных" ребер. Однако в данном доказательстве почти одноцветным считается ребро, в котором есть не менее п — t + 2 вершин (п и t — параметры из условия теоремы 14), покрашенных в один и тот же цвет. Как и в §2.7, ребрам, которые были почти одноцветными в начале процесса перекраски, запрещается становиться полностью одноцветными в течение процесса. Отметим, что при этом анализ вероятностной конструкции становится качественно другим. Подобный подход к построению случайной r-раскраски вершин гиперграфа позволяет получить при малых (по сравнению с п) значениях г существенно более сильный результат для класса (п, /)-систем по сравнению с классом всех п-однородных гиперграфов или с конструкцией для простых гиперграфов из §2.7.

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

В параграфе 3.1 обсуждается задача об оценках максимальной степени вершины в однородных гиперграфах с большим хроматическим числом и большим обхватом. Простым циклом длины s (s-циклом) в гиперграфе Н называется последовательность (Ло, vq,A\,..., As-\, vs-i, Л5), где Ао, ■.., Л8_1 — различные ребра Н, ребро As совпадает с Ло, а ь'о,..., vs~i — различные вершины Н, причем Vi 6 Ai П Ai+i для всех i = 0,..., s — 1. Обхватом гиперграфа Н называется длина минимального простого цикла в Н. Обхват гиперграфа Н обозначается через д(Н).

В первых двух главах изучались величины Д(п,г) и А*(п,г), равные минимально возможному значению максимальной степени вершины гиперграфа в классе n-однородных и, соответственно, тг-однородных простых гиперграфов, которые не являются r-раскрашиваемыми. Подобная же задача для

класса гиперграфов с большим обхватом была формально предложена Косточкой и Рёдлем31, но реально она изучалась еще в работе Эрдеша и Ловаса11 1973 г., которые собственно впервые и доказали существование однородных гиперграфов со сколь угодно большими и хроматическим числом, и обхватом.

Обозначим через Д(п,г, 5) минимально возможное значение максимальной степени вершины гиперграфа в классе п-однородиых гиперграфов с хроматическим числом больше г и обхватом больше s, т.е.

А(п, г, s) = min {Д(Я) : Я — n-однородный, х(Я) > г, g(H) > s} .

Легко понять, что Д(тг,г, 1) = Д(п,г), а Д(тг,г, 2) = Д*(п,г).

Задача о нахождении величины Д (n,r, s) при s > 2 нетривиальна уже для случая графов, п = 2. В частном случае для графов без треугольников, s = 3, она была поставлена еще В.Г. Визиигом32 в 1968 году, а ее исследованию посвящено большое количество работ, среди авторов которых мы выделим A.B. Косточку, В. Воллобаша, О.В. Бородина, П. Кэтлина, Дж. Лоуренса, Дж. Кима и А. Йохаиссена. На сегодняшний день известно, что для любых г ^ 2 и s ^ 3 выполнены следующие неравенства: .

С г In г < Д(2, г, 3) ^ Д(2, г, s) < |"2rlnr],

где С S (0,1) — некоторая абсолютная константа. Таким образом, хоть задача для графов не решена даже асимптотически, порядок роста величины Д(2,г, s) ясен. В случае же гиперграфов появляется второй параметр однородности п, и все становится намного сложнее.

Основными результатами §3.1 являются новые асимптотические нижние оценки величин А(п,г, 3) и Д(п, г, 5). Более того, оказывается, что имеют место более сильные результаты относительно максимальной реберной степени в однородных гиперграфов с большим хроматическим числом и большим обхватом. Первый из них сформулирован в теореме 15.

Теорема 15. Существует такое натуральное число щ, что для всех п > По, всех г ^ 2 и любого п-однородного гиперграфа Я с условиям д{Н) > 3 и

Де(Я) < Г"-У - 1,

выполнено х(Я) < г.

Простым следствием теоремы 15 является новая нижняя оценка величины Д(п,г,3).

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

Следствие 3. Существует такое натуральное число щ, что для всех п > по и всех г>2 выполнено неравенство

Л(п,г,3) ^r—V4^15^ • (15)

Оценка (15) асимптотически улучшает все предыдущие результаты в широкой области значений параметров In г = 0(п2п~3), и кроме того, она достаточно близка к наилучшей верхней оценке Косточки и Рёдля31:

A(n,r,s) ^ |~nrn_1lnr~| для любых п, г, s ^ 2.

Зазор между ними имеет порядок всего лишь n1+0^'lnr.

Второй результат §3.1 дополнительно усиливает нижнюю оценку максимальной степени вершины, если гиперграф имеет обхват не менее 6. Выполнена следующая теорема о величине Л(п,г,5).

Теорема 16. Существует такая константа с > 0, что для любых п ^ 3, г > 2 выполняется неравенство

Д(п,г,5) > с^-. (16)

Новая оценка (16) улучшает все ранее известные результаты в очень широкой области значений параметров: In г = О j .

Теорема 16 является простым следствием следующего утверждения, дающего достаточное условие r-раскрашиваемости однородного гиперграфа с большим обхватом.

Теорема 17. Существует такая абсолютная константа с > 0, что для любых натуральных чисел n ^ 3, г ) 2 и произвольного п-одпородного гиперграфа H, удовлетворяющего условиям: д(Н) > 5 и

Inn

выполнено х(Н) ^ г. Более того, достаточно взять с = 1/110.

Отметим, что полученные оценки (15), (16) величин Д(п,г,3) и Д(п,г,5) являются единственными нетривиальными (т.е. напрямую не следующими из аналогичных оценок для случая простых гиперграфов) на сегодняшний день нижними оценками Д(п, г, s) при п > 2 и s > 2.

Параграф 3.2 посвящен доказательству теоремы 15. Доказательство использует ту же самую конструкцию случайной раскраски, что и в §2.9 для случая (п, /)-систе.м. Однако, если гиперграф имеет обхват больше трех, эта

конструкция позволяет получить более сильный результат сразу для всех значений числа цветов г (ср. условия теоремы 14 и теоремы 15).

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

Пусть Н — гиперграф из условия теоремы 17, а V = {1,..., т} — множество его вершин. Пусть задан следующий набор независимых в совокупности случайных элементов:

1. £ = (£i,...,£m) ~ вектор из независимых одинаково распределенных случайных величин с равномерным распределением на множестве цветов {1,2.....г};

2. Ni = (Ni(t),t > 0),..., Nm = (Nm(t),t ^ 0) — стандартные пуассонов-ские процессы постоянной интенсивности 1;

3. : г = 1,... , т; к 6 N} — одинаково распределенные случайные величины, принимающие значения 1,2, ...,г с равной вероятностью р (параметр конструкции) и значение 0 с вероятностью 1 — гр.

Для каждой вершины v и цвета и 6 {1,2,... ,г} введем следующие случайные величины:

kv(u) = min jfc : т/(к) = uj , Xv(u) = min{t: Nv(t) — kv(u)} ,

kv(0 =min{fc„(u) : X„ = min{i: Nv(t) = *;„(£)} .

Процесс случайной перекраски осуществляется следующим образом. В начальный момент времени каждая вершина v покрашена в цвет £„. Как и раньше, мы выделяем почти одноцветные ребра: ребро В 6 Е(Н) является почти одноцветным с доминирующим цветом и, если выполнено событие

ЛМ(В,и) = jl < 1* ы> ^ Л|'

где 1 ^ h < тг/2 — второй параметр конструкции. Далее, для любой v е V и любого А; 6 N в момент времени Tv(k), момент fc-ro скачка пуассоновского процесса Nv, мы проверяем следующие три условия:

1 Существует ребро А, v S А, которое было одноцветным в начальной раскраске £ и ни одна из вершин А еще не сменила цвет ко времени Tv(k).

2 Выполнено ffl $ {0,U-

(к)

3 Перекраска вершины v в цвет щ не заблокирована. Мы говорим, что перекраска вершины v в цвет и заблокирована, если нашлось такое ребро В, v G В, что В было почти одноцветным с доминирующим цветом и в раскраске £ и в момент времени Xv(u) = Tv(kv(u)) вершина г; осталась единственной вершиной ребра В, не покрашенной в цвет и.

Если все три условия выполнены, то мы перекрашиваем вершину v в цвет rjvk\ Если же хотя бы одно из них не выполняется, то мы не перекрашиваем вершину v в момент времени Tv(k).

Обозначим через Çv(t) — цвет вершины v в произвольный момент времени t ^ 0. Далее, в параграфе с помощью вероятностного анализа с привлечением Локальной леммы показывается, что при некотором выборе параметров конструкции (р, h,t) случайная раскраска Ç(t) = (Ci(i)i • • •. Сm(t)) с положительной вероятностью является правильной r-раскраской для гиперграфа Н.

В параграфе 3.4 рассматривается задача типа Эрдеша - Хайнала для гиперграфов с большим обхватом. Обозначим через т(п, г, s) минимально возможное число ребер гиперграфа в классе п-однородных гиперграфов с хроматическим числом больше rue обхватом больше s. Формально определение m(n,r, s) можно записать так:

т(п, г, s) = min {\Е(Н)\ : H — n-однородный, х{Н) > г> з{Ю > s} •

Заметим, что из данного определения следуют равенства

т(п, г, 1) = т(п, г), т(п, г, 2) = т*(п, г).

Данная задача изучалась в работах Эрдеша и Ловаса11, Косточки и Кумбха-та29, Косточки и Рёдля31. В диссертации получены новые асимптотические нижние оценки величины т(п, г, s), которые опираются на следующую лемму, проясняющую связь величин m(n,r,s) и A(n,r,s).

Лемма 1. Для любых n,r, s ^ 2 выполняется неравенство

т(п+ [s/2\, г, s) > —^ (Av(n, г, S))[s/2J+1. n + L2J

Простым следствием леммы 1 и оценок (15), (16) величин Л(п,г, 3) и Д(п,г, 5) является следующее утверждение.

Следствие 4. 1) Существует такое натуральное число щ, что для всех п > По, всех г ^ 2 и s е {3,4} выполнено неравенство

т(п + [s/2\ ,r,s)> -(гп-1п~4>/кЩ|

n+ L2J V

26

2) Существует такая абсолютная константа с > 0, что для всех тг ^ 3, всех выполнено неравенство

г / rn-i\LV2J+i

Приведенные оценки т(п, г, s) улучшают предыдущий результат Косточки и Кумбхата29 в широкой области значений параметров.

В параграфе 3.5 изучаются экстремальные задачи для раскрасок неоднородных гиперграфов с большим обхватом. Нетривиальное обобщение задачи Эрдеша - Хайнала для неоднородных гиперграфов было предложено Эрде-шем и Ловасом11 в 1973 году. Пусть Я = (V, Е) — произвольный гиперграф. Обозначим через е(Н) минимальную мощность ребра в этом гиперграфе, т.е.

е{Н) = min {|е| : е е Е} ,

а также введем функцию /(Я) по правилу

ее Е

Задача, предложенная Эрдешем и Ловасом, состоит в том, чтобы найти минимальное значение функции /(Я) в классе гиперграфов Я, удовлетворяющих условиям е(Я) = п, х(Я) > 2. Искомое значение они обозначили через /(п). Таким образом,

f(n) = min {/(Я) : Я - гиперграф, е(Я) = п, х(Я) > 2} .

Вопрос о том, верно ли, что /(п) —» +оо с ростом п, был решен Беком18, а наилучшая нижняя оценка величины /(п) была получена Л. Лу33, который обосновал соотношение:

ч / A Inn

/(n)^-o(l))

Кроме того, Лу рассмотрел естественное обобщение задачи о величине /(п), связанное с r-раскрашиваемостыо неоднородных гиперграфов для произвольного г > 2. Он доказал следующее утверждение.

Теорема. (Л. Лу) Для любых г ^ 2 и е € (0, (г — 1)/4г) существует такое по = щ(£,г), что для всех п > щ и любого гиперграфа Я = (V, Е) с условиями е(Я) = п и

(--е] ¿—' ^ V 4г у In Inn

ees 4 7

выполнено х(Я) ^ г.

33L. Lu, "Он a problem of Erdös and Lovász oil coloring noil-uniform liypergraplis", www.math.sc.edu/ lu/papers/propertyB.pdf

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

Теорема 18. Пусть п ^ 3, г ^ 2, а Н = (V, Е) — произвольный гиперграф с условиями е(Н) = п и д(Н) > 3. Если, кроме того, выполняется неравенство

ее Е

то Н является г-раскрашиваемым.

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

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

Параграф 4.1 посвящен задаче A.B. Косточки о полноцветных раскрасках гиперграфов. Раскраска множества вершин гиперграфа Н = (У, Е) в г цветов называется полноцветной для Н, если в ней каждое ребро из Е содержит вершины всех цветов. В частности, полноцветная 2-раскраска является правильной двухцветной раскраской. В 2002 году A.B. Косточка34 поставил задачу об отыскании величины р(п,г), равной минимальному числу ребер гиперграфа в классе п-однородных гиперграфов, для которых не существует полноцветных г-раскрасок.

В диссертации получены новые нижние и верхние оценки величины р[п, г). Нижняя оценка сформулирована в теореме 19.

Теорема 19. Для любых п ^ 3, г ^ 3 выполнено неравенство

(17)

Оценка (17) улучшает предыдущий результат Косточки34 в асимптотической области г = о(у/п/ Inп). В следующей теореме приведена новая верхняя оценка р(п, г).

34A.V. Kostochka, "On a theorem Ъу Erd6s, Rubin and Taylor on choosability of complete bipartite graphs", Electronic Journal of Combinatorics, 9:1 (2002), research paper №9.

Теорема 20. Пусть задана функция г = г(п), удовлетворяющая условию г^З. Пусть, кроме того, функция в, — й{п) := г3/п2 не превосходит некоторой полоо/сительиой константы с < 1/2 при всех п > по. Тогда существует такая функция ф = <р(п), зависящая от функции г и стремящаяся к единице при п —у оо, что для всех п ^ по выполняется 71еравенство

> г У п Х+\А4 + 16п3г(г-1)

Заметим, что в силу условия теоремы 20 оценка (18) выполнена только для г, имеющих порядок роста О (п2/3). Для больших значений параметра г выполнена более слабая, зато верная для всех значений верхняя оценка.

Теорема 21. Для любых п ^ 2, г ^ 2 выполняется неравенство

Новые оценки (18) и (19) в совокупности улучшают предыдущую оценку Косточки34 в широкой асимптотической области г = о(п/1пп).

Параграф 4.2 посвящен обоснованию теоремы 19 о нижней оценке величины р(п,г). Доказательство основано иа применении модификации метода случайной перекраски для случая полноцветных раскрасок. Подобный метод впервые применяется в данной задаче.

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

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

Теорема. (П. Эрдеш, Л. Ловас) Пусть 2^г^пиН— п-однородиый гиперграф. Если выполняется неравенство

(19)

где

/(п, г) = шах

п2 + 2пг 3пг + ^/9п2г2 + 12п3г(г - 1)

2(г - 1)' 6(г - 1)

гп-1

то для Н существует полноцветная г-раскраска.

В диссертации получено улучшение теоремы Эрдеша и Ловаса, сформулированное в теореме 22.

Теорема 22. Пусть заданы п > г ^ 3 и Н = (V, Е) — п-однородный гиперграф с условием

Тогда, если (г — I)2 < n/lnn, то для Н существует полноцветная г-раскраска.

При г2 = о(п/\пп) теорема 22 существенно улучшает классический результат Эрдеша и Ловаса. Отметим, что подобные достаточные условия (в виде ограничения на максимальную степень ребра гиперграфа) существования полноцветных раскрасок находят применения в абстрактной теории автоматов (см., например, 35). Доказательство теоремы 22 использует конструкцию случайной раскраски из §4.2 с дополнительным привлечением Локальной леммы.

В последнем параграфе четвертой главы, параграфе 4.5, обсуждается связь задачи о нахождении величины р(п, г) с задачей о предписанных раскрасках полных r-дольных графов. В 1979 году Эрдеш, Рубин и Тейлор26 поставили вопрос о нахождении предписанного хроматического числа графа

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

т. При т > 3 точный ответ до сих пор неизвестен, однако были получены хорошие асимптотические оценки величины ch(Kmtr). Н. Алон36 показал что ch(Km,T) = G(r In т), т.е. существуют такие положительные константы ci < 1 < С2, что для всех m ^ 2, г ^ 2 выполняются неравенства

cirlnm ^ ch{Km,r) ^ С2г1пт.

В частном случае г = 2, Рубин26 нашел асимптотику величины ch{Kmf2) при растущем 7п:

ch{Kmti) = (1 + о(1)) log2m. (21)

Наконец, М. Кривелевич и Н. Газит37 обосновали, что при любом фиксированном г и растущем m выполнено следующее обобщение классического

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

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

37N. Gazit, M. Krivelevich, "On the asymptotic value of the choice number of complete multi-partite graphs", Journal of Graph Theory, 52 (2006), 123-134.

результата Рубина:

c^m,r)=,(l + 0(l))ln(r^rm_1}). (22)

В диссертации получен результат, обобщающий (21) и (22) на случай растущего значения параметра г. Выполнена следующая теорема.

Теорема 23. Пусть функция г = г(т) удовлетворяет соотношению In г = o(lnm) при т, —¥ оо. Тогда

ch(Kmtr) = (l + o(l))ln{rl™_1)y (23)

Более того, если г растет, то

ch(Kmtr) = (1 +o(l))rlnm.

Доказательство теоремы 23 опирается на тесную связь величин р(п, г) и ch {Kmtr), представленную в лемме 2, а также на результаты §4.1 об оценках р(п,г).

Лемма 2. Пусть ch (KmtT) = х, тогда

р(х — 1,г) ^ rm < гр(х,г).

Пятая глава диссертации состоит из трех параграфов и посвящена асимптотическому исследованию функции Ван дер Вардена W{n,r), впервые появившейся в знаменитой теореме Ван дер Вардена2. Напомним, что W(п, г) равна такому минимальному натуральному числу N, что в любой раскраске начального отрезка натурального ряда {1,...,7V} в г цветов найдется одноцветная арифметическая прогрессия длины го. Сама же теорема Ван дер Вардена утверждает, что такая величина существует.

В параграфе 5.1 приводится история изучения функции Ван дер Вардена, обсуждается ее тесная связь с задачами о максимальных плотностях множеств, не содержащих длинных арифметических прогрессий, а также с теорией раскрасок гиперграфов. В терминах теории гиперграфов можно дать следующее эквивалентное определение W(n,r). Для любых натуральных N > п введем гиперграф Hn(N) = (V(N), En(N)), где множество вершин есть V(N) = {1,..., iV}, а множество ребер образуют все арифметические прогрессии длины п: En(N) = {все арифметические прогрессии длины п из V(iV)}. Тогда несложно понять, что имеет место равенство:

W(n,г) = min{N : x{Hn{N)) > г}.

Тем самым, вопрос о том, выполнено ли неравенство Win, г) > N, сводится к вопросу о том, является ли гиперграф арифметических прогрессий Hn(N) r-раскрашиваемым или нет.

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

Теорема 24. Существует такое натуральное число по, что для всех п ^ щ иг ^ 2 выполняется неравенство

W(n,r) > гп-1п~^УЫп11п(2М" 15"klnn/ln(2Н" (l - ^ . (24)

Теорема 25. Существует такое число с > 0, что для всех п ^ 3 и г ^ 2 выполняется неравенство

W(n,r) ^ Су——. (25)

Inn

Оценки (24) и (25) существенно улучшают ранее известные результаты В.М. Шмидта38, 3. Сабо27, а также оценку, получающуюся простым применением теоремы Эрдеша и Ловаса11 о величине Де(п, г) (подробнее, см., например, монографию39). Легко также видеть, что вторая оценка (25) асимптотически сильнее чем (24). И на сегодняшний день она является наилучшей в очень широкой области значений параметров: In г = 0(у/п\п п). При больших значениях параметра г можно получить более сильные оценки, сочетая теорему о симметрии в гиперграфах и классические конструкции Ф. Беренда и Р. Ранкина множеств, не содержащих длинных арифметических прогрессий (подробнее, см., например, 40).

В параграфе 5.2 приведено доказательство теоремы 24. Основная его идея состоит в следующем: надо рассмотреть гиперграф арифметических прогрессий Hn(N) не только как n-однородный гиперграф с ограниченными степенями вершин, но и как гиперграф, "почти" не содержащий коротких циклов. Конечно, гиперграф Hn(N) не является даже простым, но в нем очень существенная доля пар ребер имеют не более одной общей вершины. Подобное простое наблюдение в сочетании с вероятностной техникой для раскраски простых гиперграфов было использовано Сабо27 для установления предыдущей наилучшей нижней оценки W(n, 2). В диссертации предложено дальнейшее развитие этой идеи: надо посмотреть на гиперграф арифметических

38 W.M. Schmidt, 'Two combinatorial theorems on arithmetic progressions'', Duke Mathematical Journal, 29:1 (1962), 129-140.

39T. Tao, V. Vu, Additive combinatorics, Cambridge University Press, Cambridge, 2006.

40R.L. Graham, B.L. Rotshild, J.H. Spencer, Ramsey theory, Wiley, New York, 1980.

прогрессий не только, как на "почти простой" гиперграф, а как на гиперграф, в котором "почти нет циклов длины 2 и 3". А формально, мы применяем к гиперграфу арифметических прогрессий Нп(Ы) конструкцию случайной раскраски из §3.2, использовавшуюся нами для раскраски гиперграфов с обхватом больше трех. Однако, по сравнению §3.2, анализ этой случайной конструкции существенно усложняется. В Нп(Ы) имеются циклы длины 2 и 3, что требует рассмотрения дополнительных ситуаций, в которых в пашей случайной раскраске возникают одноцветные ребра.

Параграф 5.3 посвящен доказательству теоремы 25 о второй нижней оценке функции Ван дер Вардена \У(п, г). Здесь развивается подход из §5.2, а именно гиперграф арифметических прогрессий Нп{И) рассматривается как гиперграф, в котором "почти нет" циклов малой длины, от 2 до 5. А с формальной точки зрения для доказательства г-раскрашиваемости Нп(Ы) при ТУ, не превосходящем правой части (25), мы применяем к //„(ТУ) конструкцию случайной раскраски, использовавшуюся в §3.3 для раскраски гиперграфов с обхватом больше пяти. Из-за наличия в гиперграфе арифметических прогрессий циклов малой длины анализ получающего процесса перекраски с непрерывным временем существенно усложняется по сравнению с анализом из §3.3. Приходится разбирать большое количество случаев, в которых возможно появление одноцветного ребра в течение процесса перекраски.

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

В параграфе 6.1 даются основные сведения из теории случайных подмножеств. Пусть Г — некоторое множество из ТУ элементов, а р — произвольное число из отрезка [0,1]. Случайным подмножеством Г(р) называется случайный элемент, принимающий значения во множестве всех подмножеств Г и имеющий на нем следующее распределение:

Р(Г(р) = С)=р1с?1(1-р)ЛГ-|с1

для любого С С Г. Данную модель случайного подмножества, Г(р), принято называть биномиальной (в пей, как несложно видеть, элементы Г включаются в Г(р) независимо друг от друга с вероятностью р).

Пусть <2 — семейство подмножеств Г ("свойство" подмножеств Г) . Оно называется монотонно возрастающим, если из того, что А е О. и А С В, следует, что В тоже принадлежит О,. Семейство <2 называется монотонно убывающим, если из того, что А 6 О и А Э В, следует, что В € О,. Ясно, что если система О, монотонно возрастает, то ее дополнение 2Г \ 2 — монотонно убывает.

Пусть для каждого п € N заданы множество Г„ мощности N = N(n) (N оо при п —> оо), а также монотонно возрастающая система подмножеств Q„ множества Г„. Функция р* = р*{п) € [0,1] называется пороговой вероятностью для системы {Qn,n G N}, если

• для любой последовательности р = р(п) с условием р <С р* выполнено

Р (Г„(р) 6 Qn) -> 0 при п-> оо;

• для любой последовательности р = р(п) с условием р р* выполнено

Р (Г„(р) € Q„) 1 при п -> оо.

Совершенно аналогично определяется понятие пороговой вероятности для системы монотонно убывающих семейств {Q„,n € N} (как пороговая вероятность для {2Гп \ Qn, п € N}). Замечательный факт, установленный Б. Боллобашем и Э. Томасоном41, состоит в том, что в случае монотонного семейства Qn пороговая вероятность всегда существует. Отыскание пороговых вероятностей для монотонных свойств случайных подмножеств является одной из центральных задач вероятностной комбинаторики.

Самыми известными из изучаемых моделей случайных подмножеств являются, конечно, случайные графы, качественное изучение которых началось со знаменитых работ П. Эрдеша и А. Реньи42,43 на рубеже 50-60-х годов XX века. Модель G(n, р) случайного графа Эрдеша и Реньи — это биномиальная модели случайного подмножества Гп(р), где в качестве Гп берется множество всех ребер полного графа на п вершинах. Случайные графы — это одна из центральных областей исследований вероятностной комбинаторики, им посвящено огромное число статей и монографий, среди которых стоит особо выделить книги Боллобаша44, В.Ф. Колчина45 и С. Янсона, Т. Лучака и А. Ручински46.

Естественным обобщением модели G(n, р) случайного графа является биномиальная модель случайного гиперграфа Н(п,к,р), в которой в качестве исходного множества Г„ берется множество ребер полного fc-однородного гиперграфа на п вершинах. И в шестой главе диссертации мы изучаем пороговую вероятность для монотонно возрастающего свойства гиперграфов {хроматическое число больше г}.

41В. Bollobäs, A. Thomason, 'Thresholds functions", Combinatorica, 7 (1987), 35-38.

42P. Erdös, A. Rinyi, "On the evolution of random graphs", Publications of the Mathematical Institute of of the Hungarian Academy of Sciences, 5:1-2 (I960), 17-61.

43P. Erdös, A. Rcnyi, "On random graphs I", Publ. Math. Debrecen, 6 (1959), 290-297.

44B. Bollobäs, Random graphs, Cambridge University Press, Cambridge, 2001.

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

46S. Jansen, Т. Luczak, A. Rucinski, Random graphs, Wiley-Interscience, New York, 2000.

В параграфе 6.2 рассказывается история исследования пороговой вероятности для свойства 2-раскрашиваемости случайного гиперграфа Н(п,к,р). Оказывается, при любом фиксированнолм к ^ 3 существует не только пороговая вероятность для этого свойства, но и точная пороговая вероятность. Приведем определение точной пороговой вероятности в общем случае.

Пусть для каждого п 6 N заданы множество Г„ мощности N = N(n) (N —> оо при п -> оо), а также монотонно возрастающая система подмножеств Qn множества Гп. Функция р* = р*{п) € [0,1] называется точной пороговой вероятностью для системы {Qn,n £ N}, если

• для любого е > 0 и для любой последовательности р = р(п) с условием р < (1 — е)р* выполнено

р (Г„(р) е Qn) -> о при п ->• оо;

• для любого £ > 0 и для любой последовательности р = р(п) с условием р ^ (1 + е)р* выполнено

Р (Гп(р) S Q„) —> 1 при п -> оо.

Исследование вопроса о точной пороговой вероятности для свойства 2-раскра-шиваемости случайного гиперграфа Н(п,к,р) началось с неопубликованной работы Н. Алона и Дж. Спенсера47, в которой ими получены верхние и нижние оценки данной функции. В дальнейшем, эту проблему изучали М. Кри-велевич, Дж. Ким, П. Тетали, Д. Ахлиоптас, К. Мур, однако установить значение точной пороговой вероятности для свойства 2-раскрашиваемости Н(п,к,р) при фиксированном к ^ 3 пока не удалось.

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

Вопрос об асимптотическом поведении хроматического числа случайного графа G(n,p) изучался в знаменитых работах Б. Боллобаша48 и Т. Луча-ка49, в которых им удалось решить эту проблему в области р = Г2(1/п) . Аналогичные же результаты относительно хроматического числа Н(п, к, р) были получены Э. Шамиром50 для фиксированного к > 2 и р > п-£, а также М. Кривелевичем и Б. Судаковым51 для почти всех остальных значений

47N. Alón, J. Spencer, "A note on coloring random k-sets", unpublished manuscript

48B. Bollobás, "The chromatic number of random graphs", Combinatories, 8:1 (1988), 49-56.

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

50E. Shamir, "Chromatic number of random hypergraphs and associated graphs", Adv. Comput. Res., 5

(1989), 127-142.

р = р(п). В своих работал перечисленные авторы использовали различные результаты теории вероятностей о концентрации вероятностных мер (неравенства типа Талаграна, неравенство Янсона, неравенства больших уклонений для мартингалов и др.). Однако даже столь мощные инструменты позволяют отыскать точную пороговую вероятность r-раскрашиваемости Н(п, к, р) при фиксированных гик только в случае, когда г достаточно велико по отношению к к (как минимум, должно быть выполнено г = Г2(/с4)). В свою очередь, методы, применявшиеся Ахлиоптасом и Муром52 для исследования 2-раскрашиваемости Н(п,к,р), невозможно напрямую перенести на случай фиксированного г > 2, а при любом растущем к = к(п) они вообще не работают.

В параграфе 6.4 диссертации получены нижние оценки пороговой вероятности r-раскрашиваемости случайного гиперграфа Н(п, к,р) в случае растущих функций г = г(п) и к = к(п). Первая из них приведена в теореме 26.

Теорема 26. Пусть целочисленные функции k = к(п) ^ 3 и г = r(n) ^ 3 удовлетворяют соотношению

3 \ г*"1 ,

— In п —» +00 при п —> оо.

Тогда если

128J ^к

P = р(п) <

гк-

16F/2 (»)'

lim Р(Х(Н(п,к,р)) <г) = 1.

п—юо

Вторая нижняя оценка пороговой вероятности r-раскрашиваемости случайного гиперграфа Н(п,к,р) усиливает результат теоремы 26, когда г = г(п) и к = к(п) не слишком быстро растут.

Теорема 27. Пусть целочисленные функции k = к(п) ^ 3 и г = r(n) ^ 2 удовлетворяют соотношениям

г < к1/ы, г2к~2кА = о(п), rk-ik--iKKr) _ ln„ +0Q при п 00>

где е(к,г) =

min ' Ък- -lnjL

21пг ' 2 In((4/3) ln/c)

Р = р(п) ^

Тогда если

гк 1 п

2 fci+з/е(к,г) "ÖJ'

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

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

то

lim Р(\(Н(п,к,р)) < г) = 1.

П—>00

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

Доказательство теоремы 26 опирается на результат первой главы о величине А(п, г), нижняя оценка (4) которой дает достаточное условие г-раскра-шиваемости однородного гиперграфа в терминах ограничения на максимальную степень вершины. Доказательство же теоремы 27 использует теорему 13 второй главы о достаточном условии r-раскрашиваемости (п, /)-систем.

Благодарности

Автор выражает благодарность коллективу кафедры теории вероятностен механико-математического факультета МГУ (заведующий кафедрой — академик РАН А.Н. Ширяев) за творческую атмосферу, способствовавшей активной научной деятельности, и за поддержку при подготовке работы. Автор также искренне благодарен своим соавторам: профессору A.M. Райгородско-му, A.B. Купавскому и А.П. Розовской, за многочисленные плодотворные обсуждения задач и результатов диссертации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[14] D. A. Shabanov, "On r-chromatic hypergraphs", Discrete Mathematics, 312:2 (2012), c. 441-458.

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

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

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

Подписано в печать: 15.01.2013 Объем: 2,0 п.л. Тираж: 200 экз. Заказ № 34 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495) 363-78-90; www.reglet.ru

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

О ^ 2 013 £1 в На правах рукописи

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

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

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

Диссертация на соискание ученой степени доктора физико-математических наук

Москва —

2012

Содержание

Введение 4

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

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

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

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

§1.3 Доказательство первой оценки в задаче Эрдеша Хайнала . . 27 §1.4 Метод случайной перекраски в проблеме Эрдегпа Хайнала . 30 §1.5 Доказательство второй оценки в задаче Эрдеша - Хайнала . . 41 §1.6 Экстремальные задачи для максимальных реберных и вершинных степеней гиперграфа...................43

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

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

§1.8 Задача Эрдеша - Хайнала для предписанных раскрасок .... 51 §1.9 Доказательство нижней оценки в задаче Эрдеша-Хайнала для

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

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

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

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

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

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

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

§2.6 Доказательства нижних оценок в задаче Эрдеша - Ловаса ... 88 §2.7 Доказательство нижней оценки максимальной степени ребра

в простых гиперграфах с большим хроматическим числом ... 91 §2.8 Оценки максимальной реберной степени в (п, /)-системах с большим хроматическим числом....................114

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

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

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

§3.1 Оценки максимальной стегюии вершины в графах и гиперграфах с большим хроматическим числом и большим обхватом . . 137 §3.2 Доказательство оценки максимальної! степени ребра в гиперграфах с большими хроматическим числом и обхватом больше

трех..................................144

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

пяти .................................161

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

обхватом...............................182

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

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

приложения 198

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

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

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

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

Глава 5. Функция Ван дер Вардена и раскраски гиперграфов 231 §5.1 Теорема Ван дер Вардена об арифметических прогрессиях . . 231 §5.2 Доказательство нижней оценки функции Ван дер Вардена . . 241 §5.3 Доказательство второй оценки функции Ван дер Вардена . . . 273

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

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

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

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

графа.................................300

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

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

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

Введение

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

Приведем ряд основных определений. Гиперграфом Н называется пара множеств Н = (У:Е), где 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 в. установить ряд замечательных фактов из ана-

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

Одним из главных инициаторов �