авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --
Федеральное государственное бюджетное учреждение наук

и Институт проблем передачи информации им. А.А. Харкевича Российской академии наук

На правах рукописи

УДК 519.212.2, 519.112.7 Шабанов Дмитрий Александрович Экстремальные и вероятностные задачи теории гиперграфов и аддитивной комбинаторики 01.01.05 теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

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

Официальные оппоненты: доктор физико-математических наук, профессор, Кабатянский Григорий Анатольевич, главный научный сотрудник Института проблем передачи информации им. А.А. Харкевича РАН доктор физико-математических наук, профессор, Павлов Юрий Леонидович, заведующий лабораторией Института прикладных математических исследований Карельского научного центра РАН доктор физико-математических наук, профессор, Шкредов Илья Дмитриевич, ведущий научный сотрудник Математического института им. В.А. Стеклова РАН

Ведущая организация: Хабаровское отделение Института прикладной математики Дальневосточного отделения РАН

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

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

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

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

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

.

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

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

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

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

Экстремальные задачи о раскрасках гиперграфов впервые возникли в клас сических работах 20-30-х годов XX века, положивших начало теории Рамсея.

Проблемы рамсеевского типа берут свое начало в комбинаторике с теоремы Рамсея1 1930 года, а в теории чисел с теоремы Ван дер Вардена2 1927 года.

Обе эти теоремы очень тесно связаны с раскрасками гиперграфов и, по сути, стимулировали само развитие теории раскрасок гиперграфов.

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

Теорема. (Ф. Рамсей, 1930) Существует такое минимальное натураль ное число R(s1,..., st ;

k), что если n R (s1,..., st ;

k), то при любом упо F.P. Ramsey, On a problem of formal logic, Proc. of London Math. Society Ser. 2, 30 (1930), 264–286.

B.L. van der Waerden, “Beweis einer Baudetschen Vermutung”, Nieuw Archief voor Wiskunde, 15 (1927), 212–216.

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

Величину R(s1,..., st ;

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

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



2).

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

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

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

B. Sudakov, “Recent developments in extremal combinatorics: Ramsey and Turn type problems”, a Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010, 2579–2606.

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

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

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

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

Используемое сегодня понятие правильной раскраски гиперграфа было предложено П. Эрдешем и А. Хайналом6 в 1966 году. Согласно их опреде лению раскраска множества вершин V гиперграфа H = (V, E) называется правильной, если в этой раскраске все ребра из E не являются одноцветны ми (т.е. содержат вершины разных цветов). Хроматическим числом гипер графа H называется минимальное число цветов, требуемое для правильной раскраски вершин этого гиперграфа. Мы будем обозначать хроматическое число гиперграфа H через (H). Если (H) r, т.е. для гиперграфа H су ществует правильная раскраска вершин в r цветов, то говорят, что H явля ется r-раскрашиваемым. Подобное определение хроматического числа очень хорошо сочетается с другими характеристиками гиперграфа (число незави симости, максимальная степень вершины и т.п.), позволяя сохранить ту же самую взаимосвязь между ними, что и в обычных графах. Как и для гра фов, с точки зрения вычислений проблема r-раскрашиваемости гиперграфа в общем случае является NP-полной, а проблема нахождения хроматического NP-трудной7. В связи с этим естественным образом возник вопрос числа P. Erds, A. Hajnal, “On chromatic number of graphs and set–systems”, Acta Mathematica of the Academy o of Sciences, Hungary, 17:1–2 (1966), 61–99.

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

Freeman and Company, 1979.

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

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

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

Экстремальным задачам типа Эрдеша – Хайнала о раскрасках графов и гиперграфов посвящены работы таких классиков комбинаторики, как П. Эр деш, А. Хайнал, Н. Алон, Дж. Спенсер, Л. Ловас, П. Сеймур, Й. Бек, В.

Рёдль, Б. Боллобаш, а также таких известных математиков, как А. В. Ко сточка, Д. Мубаи, А. Фриз, П. Тетали, З. Сабо, Дж. Ким, Дж. Радхакришнан, А. Сринивасан, А. Плухар и многих других. Подробнее о результатах пере численных авторов можно прочитать, например, в обзорах 9, 10. Результаты относительно задачи Эрдеша – Хайнала и ее обобщений нашли применение в теории Рамсея, теории графов, аддитивной комбинаторике, теории случай P. Erds, A. Hajnal, “On a property of families of sets”, Acta Mathematica of the Academy of Sciences, o Hungary, 12:1–2 (1961), 87–123.

A.V. Kostochka, “Color-Critical Graphs and Hypergraphs with Few Edges: A Survey”, More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15, eds. E. Gyri, G. O. H. Katona, L. Lovsz, Springer, o a 2006, 175–198.

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

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

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

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

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

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

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

Второй замечательной вероятностной техникой, получившей качественное развитие в задачах о раскрасках гиперграфов, является “полуслучайный” ме тод (в зарубежной литературе принято название semi-random или nibble ме тод). Впервые основные идеи этого метода появились в работе М. Айтаи, Я.

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

P. Erds, L. Lovsz, “Problems and results on 3-chromatic hypergraphs and some related questions”, Innite o a and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, 10, Amsterdam: North Holland, 1973, 609–627.

M. Ajtai, J. Komlo, J. Pintz, J. Spencer, E. Szemerdi, “Extremal uncrowded hypergraphs”, Journal of s e Combinatorial Theory A, 32:3 (1982), 321–335.

V. Rdl, “On a packing and covering problem”, European Journal of Combinatorics, 6:1 (1985), 69–78.

o P. Erds, H. Hanani, “On a limit theorem in combinatorial analysis”, Publ. Math. Debrecen, 10 (1963), o 10–13.

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

J.H. Kim, “On Brook’s theorem for sparse graphs”, Combinatorics, Probability and Computing, 4 (1995), 97–132.

A. Frieze, D. Mubayi, Coloring simple hypergraphs, arxiv:0809.2979v Наконец, еще одним достижением вероятностных исследований в области раскрасок гиперграфов является метод случайной перекраски. Данный ме тод в комбинаторной форме был впервые предложен Й. Беком18 в связи с задачей Эрдеша – Хайнала о величине m(n, r). В дальнейшем, метод случай ной перекраски развивался в работах Дж. Спенсера, Дж. Радхакришнана, А. Сринивасана, З. Сабо, А.В. Косточки, В. Рёдля и зарекомендовал себя, как один из наиболее эффективных инструментов в экстремальных задачах о раскрасках гиперграфов.

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

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





Цель работы.

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

диссертации являются • исследование экстремальной задачи Эрдеша – Хайнала о раскрасках ги перграфов, • исследование экстремальной задачи Эрдеша – Ловаса о раскрасках про стых гиперграфов, J. Beck, “On 3-chromatic hypergraphs”, Discrete Mathematics, 24:2 (1978), 127–137.

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

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

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

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

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

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

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

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

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

7. Получено новое достаточное условие r-раскрашиваемости неоднородного гиперграфа H = (V, E) с обхватом больше трех в терминах ограничения r1|e|.

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

9. Найдена асимптотика предписанного хроматического числа полного r дольного графа с равным размером долей m в широкой области значений параметров ln r = o(ln m).

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

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

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

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

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

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

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

А.А. Харкевича, МФТИ и других высших учебных заведениях и научных центрах. Результаты диссертации могут составить содержание специальных курсов для студентов и аспирантов.

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

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

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

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

3. Семинар Теория вероятностей и статистическая физика, механико математический факультет МГУ имени М.В.Ломоносова, руководители профессор Б.М. Гуревич, профессор В.И. Оселедец, профессор С.А.

Пирогов (ноябрь 2011).

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

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

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

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

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

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

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

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

Латышев, профессор А.В. Михалев (декабрь 2010).

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

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

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

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

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

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

18. Семинар Современные проблемы теории чисел, Математический ин ститут им. В.А. Стеклова РАН, руководители член-корр. РАН С.В.

Конягин, профессор И.Д. Шкредов (май 2011, декабрь 2011).

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

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

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

1. Fete of Combinatorics and Computer Science, Кестхей, Венгрия, 11 – августа 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, Атланта, США, – 28 мая 2011 г.

7. Innite and nite sets, Будапешт, Венгрия, 13 июня – 17 июня 2011 г.

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

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

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

Публикации.

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

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

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

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

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

Гиперграфом называется пара множеств H = (V, E), где V = V (H) есть некоторое конечное множество, называемое множеством вершин гипергра фа, а E = E(H) это совокупность подмножеств множества V, которые называются ребрами гиперграфа. Гиперграф является n-однородным, если каждое его ребро содержит ровно n вершин. Раскраской множества вершин гиперграфа H = (V, E) называется произвольное отображение f : V C, где C некоторое множество, называемое множеством цветов. Если |C| = r, то раскраска f называется r-цветной или r-раскраской. Раскраска множества вершин V гиперграфа H = (V, E) называется правильной, если в этой рас краске все ребра из E не являются одноцветными. Хроматическим числом (H) гиперграфа H называется минимальное число цветов, требуемое для правильной раскраски вершин этого гиперграфа. Если (H) r, т.е. для ги перграфа H существует правильная раскраска вершин в r цветов, то говорят, что H является r-раскрашиваемым.

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

m(n, r) = min {|E(H)| : H n-однородный гиперграф, (H) r}.

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

Эти результаты сформулированы в следующих двух теоремах.

Теорема 1. Для любых n 3, r 2 выполняется неравенство 1 1 r e 12(n1) (n 1) 2 2r rn+2/r.

m(n, r) (1) e Теорема 2. Для любых n 3, r 3 выполняется неравенство 1 1/2 n m(n, r) nr. (2) Нижние оценки (1) и (2) величины m(n, r) в совокупности улучшают преды дущие результаты П. Эрдеша19, Н. Алона20, А.В. Косточки21 и А. Плухара в широкой асимптотической области значений параметров n и r:

r=3иr 1/8 ln((ln n)/2).

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

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

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

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

Степенью же ребра f в гиперграфе H называется количество других ребер P. Erds, “On a combinatorial problem, I”, Nordisk Mat. Tidskrift, 11 (1963), 5–10.

o N. Alon, “Hypergraphs with high chromatic number”, Graphs and Combinatorics, 1 (1985), 387–389.

A.V. Kostochka, “Coloring uniform hypergraphs with few colors”, Random Structures and Algorithms, 24: (2004), 1–10.

A. Pluhr, “Greedy colorings for uniform hypergraphs”, Random Structures and Algorithms, 35:2 (2009), a 216–221.

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

H, которые имеют непустое пересечение с f. Максимальная степень вершины в гиперграфе H обозначается через (H), а максимальная степень ребра через e (H).

По аналогии с задачей Эрдеша – Хайнала рассматриваются экстремаль ные величины (n, r) и e (n, r), равные минимально возможному значению (H) и e (H), соответственно, где H n-однородный гиперграф с хрома тическим числом больше r. Другими словами, (n, r) = min {(H) : H n-однородный, (H) r}, e (n, r) = min {e (H) : H n-однородный, (H) r}.

Основным результатом §1.6 является новая нижняя оценка величины e (n, r).

Теорема 3. Для любых n 3иr 3 выполняется неравенство 1 1/2 n e (n, r) nr. (3) Оценка (3) улучшает предыдущие результаты Эрдеша и Ловаса11 и Ко сточки, М. Кумбхата, В. Рёдля24 в широкой асимптотической области значе ний параметров n и r:

r=3иr= ln ln n.

Следствием из теоремы 3 является новая нижняя оценка величины (n, r).

Следствие 1. Для любых n 3иr 3 выполняется неравенство 1 1/2 n (n, r) n r. (4) В параграфе 1.7 также с помощью вероятностной конструкции из §1.4 до казывается теорема 3.

Параграф 1.8 посвящен обобщению классической задачи Эрдеша – Хай нала для предписанных раскрасок. Пусть H = (V, E) гиперграф с множе ством вершин V и множеством ребер E, а C некоторое множество, элемен ты которого называются цветами. Вершинным предписанием A называется отображение, которое каждой вершине v ставит в соответствие некоторое (непустое) подмножество A(v) C. Если |A(v)| = r для любой вершины v V, то говорят, что мощность предписания A равна r.

Раскраской f вершин графа G, соответствующей предписанию A, называ ется такое отображение f : V C, что f (v) A(v) для любого v V. При A.V. Kostochka, M. Kumbhat, V. Rdl, “Coloring uniform hypergraphs with small edge degrees”, Fete of o Combinatorics and Computer Science, Bolyai Society Mathematical Studies, 20, Springer, 2010, 213–238.

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

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

Тейлора26.

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

mlist (n, r) = min {|E(H)| : H n-однородный гиперграф, ch(H) r}.

В силу очевидного неравенства ch(H) (H) для произвольного гиперграфа H, соотношение между величинами mlist (n, r) и m(n, r) будет обратным:

mlist (n, r) m(n, r).

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

Теорема 4. Для любых n 3иr 3 выполняется неравенство 1 1/2 n mlist (n, r) nr. (5) Оценка (5) асимптотически улучшает все ранее известные результаты при всех r 3.

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

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

P. Erds, A.L. Rubin, H. Taylor, “Choosability in graphs”, Proc. West Coast Conference on Combinatorics, o Graph Theory and Computing, 26, 1980, 125–157.

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

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

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

Теорема 5. Существует такое натуральное число n0, что для всех n n и всех r 2, удовлетворяющих соотношению r n1/9, выполнено неравен ство 1 2n2 6/t m (n + 1, r) r n, (6) ln n ln n где t = t(n + 1, r) = min ln r, 2 ln((4/3) ln n).

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

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

1) Существует такое натуральное число n0, что для всех n n0 и для всех r, удовлетворяющих неравенству r 16 ln2 (n 1), выполнено 1 2n4 ln(n1) (n 1) m (n, r) r.

2 ln((4/3) ln(n1)) 2) Существует такое натуральное число n0, что для всех n n0 и для всех r, удовлетворяющих соотношениям 9 ln (n 1) r (n 1)1/9, выполнено ln(n1) 1 2n4 m (n, r) ln r (n 1) r.

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

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

ln r = ((2, 5)n ).

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

Подобное свойство гиперграфов может быть обобщено естественным образом для l-подмножеств множества вершин гиперграфа. Назовем (n, l)-системой n-однородный гиперграф, каждые l вершин которого содержатся (как под множество) не более чем в одном ребре гиперграфа. В мировой литературе (n, l)-системы также принято называть частичными системами Штейнера.

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

Основными результатами §2.3 являются новые оценки величины m (n, r, l).

Первая из них выполнена для всех l 3.

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

A.V. Kostochka, D. Mubayi, V. Rdl, P. Tetali, “On the chromatic number of set systems”, Random o Structures and Algorithms, 19:2 (2001), 87–98.

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

Теорема 8. Существует такая положительная константа C, что для любых n l 3 и r 2 выполняется неравенство l/(l2) m (n, r, l) C n2l/(l2) rn1 ln r. (9) Если, к тому же, r n, то 1/(l2) n2l l/(l2) rn1 ln r m (n, r, l) C. (10) l!

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

Мубаи30, Косточки и Рёдля31 в асимптотической области:

n ln r = o(l ln n), где l = l(n) + при n +.

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

Теорема 9. Для любых n l 2 и четных r 6 выполняется неравенство 1/(l1) (n 1)l1 r (n1)l/(l1) 81 n3/ m (n, r, l).

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

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

(n, r) = min{(H) : H n-однородный простой, (H) r}, т.е. (n, r) равна минимально возможному значению максимальной сте пени вершины в простом n-однородном гиперграфе с хроматическим числом больше r.

T. Bohman, A. Frieze, D. Mubayi, “Coloring H-free hypergraphs”, Random Structures and Algorithms, 36: (2010), 11–25.

A.V. Kostochka, V. Rdl, “Constructions od sparse uniform hypergraphs with high chromatic number”, o Random Structures and Algorithms, 36:1 (2010), 46–56.

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

Теорема 10. Существует такое натуральное число n0, что для всех n n0 и всех r 2, удовлетворяющих соотношению r n1/9, выполнено нера венство (n, r) rn1 n3/t, (11) ln n ln n где t = t(n, r) = min ln r, 2 ln((4/3) ln n).

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

Теорема 11. Для любых n 3, r 3 выполняется неравенство 1 n1 1/ (n, r) rn. (12) Оценка (12) является первой нетривиальной (т.е. не вытекающей из нера венства (n, r) (n, r)) нижней оценкой (n, r), которая выполнена при всех достаточно больших значениях числа цветов r.

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

Теорема 12. Пусть n 3 и r 3 натуральные числа. Если n-однород ный простой гиперграф H удовлетворяет условию 1 n1 2/ e (H) rn, то (H) r.

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

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

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

Теорема 13. Существует такое натуральное число n0, что для всех n n0, всех r 2 и l 2, удовлетворяющих соотношению n1/9(l1), r (13) а также любой (n, l)-системы H = (V, E) с условием rn1 n13/t 1, e (H) (14) ln n ln n где t = t(n, r, l) = min (l1) ln r, 2 ln((4/3) ln n), выполнено (H) r.

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

Теорема 14. Пусть заданы натуральные числа n 3, r 2, h 1, а также положительные числа k, c и. Введем обозначения ln n ln n ln n t= min,, q=, h ln r c ln( ln n) n 2 31 3, 2 = + k, 3 = + + k.

1 = 1 + ck 2c 2 7ck Пусть H = (V, E) (n, h + 1)-система с максимальной степенью ребра e (H) = d, причем выполнено неравенство rn1 n1k/t 1.

d Если, кроме того, выполняются соотношения t k, q, 1 0, 2 0, 3 0, k n ln n 13 e 3 3 n1 + ( k + 1)2 n2 + + n, 2n ( k + 1)3 k e то гиперграф H является r-раскрашиваемым.

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

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

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

В параграфе 3.1 обсуждается задача об оценках максимальной степени вершины в однородных гиперграфах с большим хроматическим числом и большим обхватом. Простым циклом длины s (s-циклом) в гиперграфе H на зывается последовательность (A0, v0, A1,..., As1, vs1, As ), где A0,..., As различные ребра H, ребро As совпадает с A0, а v0,..., vs1 различные вершины H, причем vi Ai Ai+1 для всех i = 0,..., s 1. Обхватом ги перграфа H называется длина минимального простого цикла в H. Обхват гиперграфа H обозначается через g(H).

В первых двух главах изучались величины (n, r) и (n, r), равные ми нимально возможному значению максимальной степени вершины гипергра фа в классе n-однородных и, соответственно, n-однородных простых гипер графов, которые не являются r-раскрашиваемыми. Подобная же задача для класса гиперграфов с большим обхватом была формально предложена Ко сточкой и Рёдлем31, но реально она изучалась еще в работе Эрдеша и Ловаса 1973 г., которые собственно впервые и доказали существование однородных гиперграфов со сколь угодно большими и хроматическим числом, и обхватом.

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

(n, r, s) = min {(H) : H n-однородный, (H) r, g(H) s}.

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

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

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

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

Теорема 15. Существует такое натуральное число n0, что для всех n n0, всех r 2 и любого n-однородного гиперграфа H с условиям g(H) 3 и ln n n1 1, e (H) r n ln(2 ln n) выполнено (H) r.

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

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

Следствие 3. Существует такое натуральное число n0, что для всех n n0 и всех r 2 выполнено неравенство ln n n1 (n, r, 3) r n. (15) ln(2 ln n) Оценка (15) асимптотически улучшает все предыдущие результаты в ши рокой области значений параметров ln r = O(n2n3 ), и кроме того, она доста точно близка к наилучшей верхней оценке Косточки и Рёдля31 :

n rn1 ln r для любых n, r, s (n, r, s) 2.

Зазор между ними имеет порядок всего лишь n1+o(1) ln r.

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

Теорема 16. Существует такая константа c 0, что для любых n 3, r 2 выполняется неравенство rn (n, r, 5) c. (16) ln n Новая оценка (16) улучшает все ранее известные результаты в очень ши 2n рокой области значений параметров: ln r = O nln n.

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

Теорема 17. Существует такая абсолютная константа c 0, что для любых натуральных чисел n 3, r 2 и произвольного n-однородного ги перграфа H, удовлетворяющего условиям: g(H) 5 и n n e (H) c r, ln n выполнено (H) r. Более того, достаточно взять c = 1/110.

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

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

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

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

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

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

(k) 3. {i : i = 1,..., m;

k N} одинаково распределенные случайные величины, принимающие значения 1, 2,..., r с равной вероятностью p (параметр конструкции) и значение 0 с вероятностью 1 rp.

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

(k) Xv (u) = min {t : Nv (t) = kv (u)}, kv (u) = min k : v = u, kv () = min {kv (u) : u {0, v }}, Xv = min {t : Nv (t) = kv ()}.

/ Процесс случайной перекраски осуществляется следующим образом. В на чальный момент времени каждая вершина v покрашена в цвет v. Как и раньше, мы выделяем почти одноцветные ребра: ребро B E(H) является почти одноцветным с доминирующим цветом u, если выполнено событие AM(B, u) = 1 I{j = u} h, j B где 1 h n/2 второй параметр конструкции. Далее, для любой v V и любого k N в момент времени Tv (k), момент k-го скачка пуассоновского процесса Nv, мы проверяем следующие три условия:

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

(k) 2 Выполнено v {0, v }.

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

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

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

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

m(n, r, s) = min {|E(H)| : H n-однородный, (H) r, g(H) s}.

Заметим, что из данного определения следуют равенства m(n, r, 2) = m (n, r).

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

Лемма 1. Для любых n, r, s 2 выполняется неравенство 1 s/2 + m (n + s/2, r, s) s (v (n, r, s)).

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

Следствие 4. 1) Существует такое натуральное число n0, что для всех n n0, всех r 2 и s {3, 4} выполнено неравенство s/2 + 1 ln n n1 m(n + s/2, r, s) r n.

ln(2 ln n) s n+ 2) Существует такая абсолютная константа c 0, что для всех n 3, всех r 2 и s 5 выполнено неравенство s/2 + rn m(n + s/2, r, s) c.

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

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

Обозначим через e(H) минимальную мощность ребра в этом гиперграфе, т.е.

e(H) = min {|e| : e E}, а также введем функцию f (H) по правилу 2|e|.

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

Таким образом, f (n) = min {f (H) : H гиперграф, e(H) = n, (H) 2}.

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

1 ln n o(1) f (n).

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

2 и (0, (r 1)/4r) существует та Теорема. (Л. Лу) Для любых r кое n0 = n0 (, r), что для всех n n0 и любого гиперграфа H = (V, E) с условиями e(H) = n и r1 ln n r1|e| 4r ln ln n eE выполнено (H) r.

L. Lu, “On a problem of Erds o and Lovsz a on coloring non-uniform hypergraphs”, www.math.sc.edu/ lu/papers/propertyB.pdf В диссертации получено существенное усиление теоремы Лу для гипергра фов с большим обхватом, которая к тому же выполнена для всех возможных значений r, а не только для фиксированных в асимптотике. Точная форму лировка звучит следующим образом.

Теорема 18. Пусть n 3, r 2, а H = (V, E) произвольный гипер граф с условиями e(H) = n и g(H) 3. Если, кроме того, выполняется неравенство 1 n 2/ 1|e| r, 2 ln n eE то H является r-раскрашиваемым.

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

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

Параграф 4.1 посвящен задаче А.В. Косточки о полноцветных раскрас ках гиперграфов. Раскраска множества вершин гиперграфа H = (V, E) в r цветов называется полноцветной для H, если в ней каждое ребро из E содер жит вершины всех цветов. В частности, полноцветная 2-раскраска является правильной двухцветной раскраской. В 2002 году А.В. Косточка34 поставил задачу об отыскании величины p(n, r), равной минимальному числу ребер гиперграфа в классе n-однородных гиперграфов, для которых не существует полноцветных r-раскрасок.

В диссертации получены новые нижние и верхние оценки величины p(n, r).

Нижняя оценка сформулирована в теореме 19.

Теорема 19. Для любых n 3, r 3 выполнено неравенство 1/3 n 1 n r p(n, r). (17) (r 1)2 ln n r 2r Оценка (17) улучшает предыдущий результат Косточки34 в асимптотиче ской области r = o( n/ ln n). В следующей теореме приведена новая верхняя оценка p(n, r).

A.V. Kostochka, “On a theorem by Erds, Rubin and Taylor on choosability of complete bipartite graphs”, o Electronic Journal of Combinatorics, 9:1 (2002), research paper №9.

Теорема 20. Пусть задана функция r = r(n), удовлетворяющая условию r 3. Пусть, кроме того, функция d = d(n) := r3 /n2 не превосходит неко торой положительной константы c 1/2 при всех n n0. Тогда суще ствует такая функция = (n), зависящая от функции r и стремящаяся к единице при n, что для всех n n0 выполняется неравенство n n2 + n4 + 16n3 r(r 1) 1 r p(n, r) e (ln r). (18) r1 4(r 1) r Заметим, что в силу условия теоремы 20 оценка (18) выполнена только для r, имеющих порядок роста O n2/3. Для бльших значений параметра r о выполнена более слабая, зато верная для всех значений верхняя оценка.

Теорема 21. Для любых n 2, r 2 выполняется неравенство n r e2 (f (n, r) ln r + 2), p(n, r) (19) r где n2 + 2nr 3nr + 9n2 r2 + 12n3 r(r 1) f (n, r) = max,.

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

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

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

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

Теорема. (П. Эрдеш, Л. Ловас) Пусть 2 r nиH n-однородный гиперграф. Если выполняется неравенство rn e (H), 4(r 1)n то для H существует полноцветная r-раскраска.

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

Теорема 22. Пусть заданы n r 3 и H = (V, E) n-однородный гипер граф с условием n 1 n r 1.

e (H) (20) (r 1)2 ln n r 8r Тогда, если (r 1)2 n/ ln n, то для H существует полноцветная r раскраска.

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

В последнем параграфе четвертой главы, параграфе 4.5, обсуждается связь задачи о нахождении величины p(n, r) с задачей о предписанных раскрас ках полных r-дольных графов. В 1979 году Эрдеш, Рубин и Тейлор26 по ставили вопрос о нахождении предписанного хроматического числа графа Kmr = Km,...,m, полного r-дольного графа с одинаковым размером долей m. При m 3 точный ответ до сих пор неизвестен, однако были получе ны хорошие асимптотические оценки величины ch(Kmr ). Н. Алон36 показал что ch(Kmr ) = (r ln m), т.е. существуют такие положительные константы c1 1 c2, что для всех m 2, r 2 выполняются неравенства c1 r ln m ch(Kmr ) c2 r ln m.

В частном случае r = 2, Рубин26 нашел асимптотику величины ch(Km2 ) при растущем m:

ch(Km2 ) = (1 + o(1)) log2 m. (21) Наконец, М. Кривелевич и Н. Газит37 обосновали, что при любом фикси рованном r и растущем m выполнено следующее обобщение классического F. Gcseg, B. Imreh, A. Pluhr, “On the existance of nite isomorphic complete systems of automata”, J.

e a of Automata, Languages and Combinatorics, 3:2 (1998), 77–84.

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

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

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

ln m ch(Kmr ) = (1 + o(1)). (22) ln (r/(r 1)) В диссертации получен результат, обобщающий (21) и (22) на случай рас тущего значения параметра r. Выполнена следующая теорема.

Теорема 23. Пусть функция r = r(m) удовлетворяет соотношению ln r = o(ln m) при m. Тогда ln m ch(Kmr ) = (1 + o(1)). (23) ln (r/(r 1)) Более того, если r растет, то ch(Kmr ) = (1 + o(1)) r ln m.

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

Лемма 2. Пусть ch (Kmr ) = x, тогда p(x 1, r) rm rp(x, r).

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

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

W (n, r) = min{N : (Hn (N )) r}.

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

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

Теорема 24. Существует такое натуральное число n0, что для всех n n0 и r 2 выполняется неравенство 1 n1 4 ln n/ ln(2 ln n) ln n/ ln(2 ln n) W (n, r) r n 15. (24) n Теорема 25. Существует такое число c 0, что для всех n 3иr выполняется неравенство rn W (n, r) c. (25) ln n Оценки (24) и (25) существенно улучшают ранее известные результаты В.М. Шмидта38, З. Сабо27, а также оценку, получающуюся простым приме нением теоремы Эрдеша и Ловаса11 о величине e (n, r) (подробнее, см., на пример, монографию39 ). Легко также видеть, что вторая оценка (25) асимп тотически сильнее чем (24). И на сегодняшний день она является наилуч шей в очень широкой области значений параметров: ln r = O( n ln n). При бльших значениях параметра r можно получить более сильные оценки, со о четая теорему о симметрии в гиперграфах и классические конструкции Ф.

Беренда и Р. Ранкина множеств, не содержащих длинных арифметических прогрессий (подробнее, см., например, 40 ).

В параграфе 5.2 приведено доказательство теоремы 24. Основная его идея состоит в следующем: надо рассмотреть гиперграф арифметических прогрес сий Hn (N ) не только как n-однородный гиперграф с ограниченными степе нями вершин, но и как гиперграф, “почти” не содержащий коротких циклов.

Конечно, гиперграф Hn (N ) не является даже простым, но в нем очень су щественная доля пар ребер имеют не более одной общей вершины. Подобное простое наблюдение в сочетании с вероятностной техникой для раскраски простых гиперграфов было использовано Сабо27 для установления предыду щей наилучшей нижней оценки W (n, 2). В диссертации предложено даль нейшее развитие этой идеи: надо посмотреть на гиперграф арифметических W.M. Schmidt, “Two combinatorial theorems on arithmetic progressions”, Duke Mathematical Journal, 29: (1962), 129–140.

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

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

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

Параграф 5.3 посвящен доказательству теоремы 25 о второй нижней оцен ке функции Ван дер Вардена W (n, r). Здесь развивается подход из §5.2, а именно гиперграф арифметических прогрессий Hn (N ) рассматривается как гиперграф, в котором “почти нет” циклов малой длины, от 2 до 5. А с фор мальной точки зрения для доказательства r-раскрашиваемости Hn (N ) при N, не превосходящем правой части (25), мы применяем к Hn (N ) конструк цию случайной раскраски, использовавшуюся в §3.3 для раскраски гипергра фов с обхватом больше пяти. Из-за наличия в гиперграфе арифметических прогрессий циклов малой длины анализ получающего процесса перекраски с непрерывным временем существенно усложняется по сравнению с анали зом из §3.3. Приходится разбирать большое количество случаев, в которых возможно появление одноцветного ребра в течение процесса перекраски.

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

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

P ((p) = G) = p|G| (1 p)N |G| для любого G. Данную модель случайного подмножества, (p), принято называть биномиальной (в ней, как несложно видеть, элементы включа ются в (p) независимо друг от друга с вероятностью p).

Пусть Q семейство подмножеств (“свойство” подмножеств ). Оно называется монотонно возрастающим, если из того, что A Q и A B, следует, что B тоже принадлежит Q. Семейство Q называется монотонно убывающим, если из того, что A Q и A B, следует, что B Q. Ясно, что если система Q монотонно возрастает, то ее дополнение 2 \ Q монотонно убывает.

Пусть для каждого n N заданы множество n мощности N = N (n) (N при n ), а также монотонно возрастающая система подмно жеств Qn множества n. Функция p = p (n) [0, 1] называется пороговой вероятностью для системы {Qn, n N}, если p выполнено • для любой последовательности p = p(n) с условием p P (n (p) Qn ) 0 при n ;

p выполнено • для любой последовательности p = p(n) с условием p P (n (p) Qn ) 1 при n.

Совершенно аналогично определяется понятие пороговой вероятности для системы монотонно убывающих семейств {Qn, n N} (как пороговая ве роятность для {2n \ Qn, n N}). Замечательный факт, установленный Б.

Боллобашем и Э. Томасоном41, состоит в том, что в случае монотонного се мейства Qn пороговая вероятность всегда существует. Отыскание пороговых вероятностей для монотонных свойств случайных подмножеств является од ной из центральных задач вероятностной комбинаторики.

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

Ручински46.

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

B. Bollobs, A. Thomason, “Thresholds functions”, Combinatorica, 7 (1987), 35–38.

a P. Erds, A. Rnyi, “On the evolution of random graphs”, Publications of the Mathematical Institute of of o e the Hungarian Academy of Sciences, 5:1–2 (1960), 17–61.

P. Erds, A. Rnyi, “On random graphs I”, Publ. Math. Debrecen, 6 (1959), 290–297.

o e B. Bollobs, Random graphs, Cambridge University Press, Cambridge, 2001.

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

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

В параграфе 6.2 рассказывается история исследования пороговой вероят ности для свойства 2-раскрашиваемости случайного гиперграфа H(n, k, p).

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

Приведем определение точной пороговой вероятности в общем случае.

Пусть для каждого n N заданы множество n мощности N = N (n) (N при n ), а также монотонно возрастающая система подмно жеств Qn множества n. Функция p = p (n) [0, 1] называется точной пороговой вероятностью для системы {Qn, n N}, если • для любого 0 и для любой последовательности p = p(n) с условием p (1 )p выполнено P (n (p) Qn ) 0 при n ;

• для любого 0 и для любой последовательности p = p(n) с условием p (1 + )p выполнено P (n (p) Qn ) 1 при n.

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

В параграфе 6.3 рассматривается проблема нахождения пороговой вероят ности для r-раскрашиваемости случайного гиперграфа H(n, k, p) при r 2.

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

Вопрос об асимптотическом поведении хроматического числа случайного графа G(n, p) изучался в знаменитых работах Б. Боллобаша48 и Т. Луча ка49, в которых им удалось решить эту проблему в области p = (1/n).

Аналогичные же результаты относительно хроматического числа H(n, k, p) были получены Э. Шамиром50 для фиксированного k 2 и p n, а так же М. Кривелевичем и Б. Судаковым51 для почти всех остальных значений N. Alon, J. Spencer, “A note on coloring random k-sets”, unpublished manuscript B. Bollobs, “The chromatic number of random graphs”, Combinatorica, 8:1 (1988), 49–56.

a T. Luczak, “The chromatic number of random graphs”, Combinatorica, 11:1 (1991), 45–54.

E. Shamir, “Chromatic number of random hypergraphs and associated graphs”, Adv. Comput. Res., (1989), 127–142.

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



Pages:   || 2 |
 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.