Раскраски графов и гиперграфов в экстремальной комбинаторике и комбинаторной геометрии тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Демидович Юрий Александрович

• Демидович Юрий Александрович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Демидович Юрий Александрович

4.1 История задачи

4.2 Формулировка основных определений

4.3 Формулировки основных теорем и численные результаты

4.4 Доказательства теорем

4.4.1 Доказательство теоремы

4.4.2 Доказательство теоремы

4.4.3 Доказательство теоремы

4.4.4 Доказательство теоремы

4.4.5 Доказательство предложений 2,

Заключение

Список литературы

Введение

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

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

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

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

Экстремальные задачи о раскрасках гиперграфов впервые начали изучаться в классических работах Эрдеша с соавторами в 60-х годах 20-го века. В общем виде они имеют следующую формулировку:

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

Несомненно, самой знаменитой задачей такого типа является проблема Эрдеши Хиинили. согласно которой требуется найти минимально возможное

и

ческим числом больше г. Искомую величину обозначают через т(и,г). Эта задача была поставлена П. Эрдешем и А. Хайналом в 1961 году в совместной работе [1], ей посвящены работы таких ученых, как Н. Алон, Л. Ловас, Й. Бек, Дж. Спенсер, П. Сеймур.

Именно в связи с изучением раскрасок гиперграфов были созданы важнейшие вероятностные инструменты, такие как, например, Локальная лемма,

которые нашли применения в различных областях.

Задача имеет множество обобщений. Так, в работе Д.А. Шабанова [2] было предложено изучать следующую величину. Пусть к — натуральное число. Будем называть раскраску вершин гиперграфа в г цветов к-правильной, ес-

к

тов. По аналогии с величиной т(п,г) обозначим через т&(п,г) минимально

к

раскраски в г цветов. В случае, когда г = 2, обычно (п, 2) обозначают просто через (п).

Подгиперграф И' гиперграфа И = (V, Е) называется остовным, если множество его вершин — V, а множество Е' его ребер является подмножеством Е.

гцение задачи Эрдеши Хиинили.

Введем величину т&,е(п), равную минимальному числу ребер гиперграфа п

граф с |Е'| > (1 — £)|Е| не имеет к-правпльной раскраски. При £ = 0 имеем т&,£(п) = (п). И вообще, легко показать, что при £ < тщ выполняется равенство т&,е(п) = (п).

Еще одно направление исследований диссертации связано с раскрасками случайных гиперграфов в классической биномиальной модели И(п, к,р), п > к ^ 2, п,к Е М, р Е (0,1) .В этой модели каждое подмножество из кп

р

р р = р( п) .

при к = 2 модель И(п, к,р) представляет собой классическую модель случайного графа Эрдеша-Реньи С(п,р). Случайный граф С(п,р) является одним из основных объектов изучения в вероятностной комбинаторике, его систематическое исследование началось с классических статей П. Эрдеша и А. Реньи [4] и [5]. Вышло множество работ, посвященных свойствам и характеристикам случайного графа С(п,р). Основные результаты сформировавшейся в настоящее время теории могут быть найдены в книгах [6]—[8].

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

Задача о поиске асимптотического распределения хроматического числа случайного графа G(n,p) была поставлена П. Эрдешем еще в 60-е годы XX века. В работе [9] Б. Боллобаша данная задача была решена в случае постоянного p. Для p = o(n) аналогичный результат был получен Т. Лучаком в

[10]. Большое количество работ посвящено случаю np = c = const. В этом случае хроматическое число ограничено с вероятностью, стремящейся к1. В связи с этим задачу можно переформулировать в проблему поиска порогового значения c(r), до которого хроматическое число не будет превосходить заданное значение r с вероятностью, стремящейся к 1. В настоящее время точные значения пороговой величины не найдены, но известны достаточно близкие оценки.

Первые нижние и верхние оценки порогового значения c для гиперграфов в случае p = cn/ (были получены Н. Ал оном и Дж. Спенсером в неопубликованной работе. Они оценивали пороговую вероятность наличия правильной двухцветной раскраски. Их результат последовательно улучшался в работах

[11] Д. Ахлиоптаса, Дж. Кима, М. Кривелевича и П. Тетали, [12] Д. Ахлиоп-таса и К. Мура, [13] А. Койя-Оглана и Л. Здеборовой и, наконец, наилучший результат получили А. Койя-Оглан и К. I bum Поту в [14].

В случае, когда np ^ 1, Э. Шамир и Дж. Спенсер (см. [15]) доказали, что хроматическое число G(n,p) сконцентрировано в конечном числе значений для p ^ n-1/2. Т. Лучаку удалось показать, что при p ^ n-5/6 достигается концентрация в двух последовательных значениях. Затем в [16] И. Алон и М. Кривелевич показали, что концентрация в двух значениях имеет место при p ^ n-1/2. Однако в этих работах не получены сами значения точек концентрации. Явным образом их удалось отыскать в [17] А. Койя-Оглану, К. Панайоту и А. Штегер для n-1 ^ p ^ n-3/4.

Аналогичных исследований для случайных гиперграфов, когда p(^ n, проведено не было. В настоящей диссертации нас будет интересовать именно этот случай.

В сороковые годы XX века была сформулирована одна из самых популярных задач комбинаторной геометрии — проблема Нелсони Эрдеши Хидвиге-ра. Она заключается в отыскании величины x(Rn), которая называется хроматическим числом пространства и равна минимальному числу цветов, в которые можно так покрасить все точки Rn, что никакие две точки одного цвета не находятся на расстоянии 1. Проблема не решена до сих пор даже для случая плоскости. Наилучшая нижняя оценка для величины х (R2) была получена О. ди Греем в [18], сама работа стала настоящим прорывом. Ди

Грей показал, что хроматическое число плоскости не может быть меньше 5. Для этого им был придуман дистанционный граф специального вида, вершины которого не могут быть покрашены правильным образом в 4 цвета. Верхняя оценка, утверждающая, что хроматическое число плоскости не превосходит 7, доказывается примером замощения плоскости шестиугольниками с нужным диаметром (см. [19]).

В случае произвольной размерности, когда вместо точек плоскости рассматриваются точки пространства Rn, зазор с ростом n становится только больше. Для n = 3 известно лишь, что 6 ^ х (R3) ^ 15 (см. [20], [21]). Ма-n

асимптотический случай, т.е. случай, когда n ^ то. В 1981 году в работе [28] П. Франкл и Р. Уилсон установили, что хроматическое число пространства растет экспоненциально, и подтвердили тем самым гипотезу П. Эрдеша:

X (Rn) ^ (1.207... + o(1))n , n ^ то.

Затем эта нижняя оценка была усилена в [29], [30] A.M. Райгородским, результат которого является наилучшим на настоящий момент:

X (Rn) ^ (1.239 ... + o(1))n , n ^ то.

Тем не менее, верхняя оценка довольно далека от нижней. Д. Ларман и К. Роджерс в [31] показали, что

X (Rn) < (3 + o(1))n , n ^ то.

Конечно, у задачи Нелсони Эрдеши Хидвигери появилось множество обобщений и переформулировок. Например, вместо одного запрета можно рассмотреть набор из нескольких запрещенных расстояний (см. [24], [29]). Возможна и модификация с запретом определенных конфигураций, таких как, например, одноцветные симплексы с определенными параметрами (см. [32], [33], [34], [35]). В 1976 году М. Венда и М. Пер лес в [36] предложили рассматривать случай рационального пространства. В настоящей диссертации будет изучено асимптотическое поведение хроматических чисел рациональных пространств с различными метриками.

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

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

1

совпадает с хроматическим числом пространства Rn. По теореме Эрдеша-де Брейна (см. [37]) для вычисления значения х (Rn) достаточно ограничиться исследованием конечных дистанционных графов.

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

Первый результат подобного типа был получен П. Эрдешем в [38]. Ему удалось доказать, что для заданных положительных целых k и £ существует граф, которого хроматическое число которого больше k, и при этом в нем

£

клик размера не менее 3).

Впоследствии Эрдеш в [39] задался следующим вопросом: существует ли дистанционный граф на плоскости с хроматическим числом 4, который не содержит треугольников?

Пример такого графа был представлен Н. Уормалдом в [40]. Его результат был в некотором смысле усилен Р. Хохбергом в [41] и П. О'Доннеллом в [42], [43].

Е.Е. Демехиным, О.И. Рубановым, A.M. Райгородским в [44] и позже А.Б. Купавским в [45] была изучена величина, равная максимуму хроматических чисел дистанционных графов в Rn, которые не содержат полных подграфов заданного размера. Мы уточним некоторые из их результатов. Упомянутая величина представляет интерес также в случае рационального пространства и будет исследована в настоящей диссертации.

Цель работы и основные задачи

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

n

однородном гиперграфе, не допускающем раскраски в 2 цвета, в которой

k

2. изучение феномена концентрации хроматического числа случайно го к-однородного гиперграфа И(п,к,р) на п вершинах при р(&&) ^ п, что соответствует неразреженному случаю;

3. исследование асимптотических нижних оценок хроматических чисел рациональных пространств с метрикой 1и для отдельных иррациональных значений запрещенного расстояния в растущей размерности;

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

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

Все результаты диссертации являются новыми и состоят в следующем:

1. получены новые нижние оценки величины (п), равной минимальному

п

к

вершин обоих цветов;

2. получены новые нижние оценки для величины т&,£(п), равной мини-

п

товный подгиперграф с числом ребер, равным (1 — £), умноженным на число ребер исходного гиперграфа, не допускает раскраски всех вершин

к

обоих цветов;

с ку

в биномиальной модели И(п,к,р), к ^ 4, р(^ п, имеет предельную концентрацию в двух или трех значениях в зависимости от параметра р = р( п) ,

4. получены новые нижние асимптотические оценки хроматических чисел X ((0П, /и) , ё) рациональных пространств с метрикой 1и при и ^ 2 и ё = и2ра, где р — простое, а а Е М, для растущего п;

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

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

Теоретическая и практическая ценность полученных результатов

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

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

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

Степень достоверности и аппробация результатов

Все результаты работы строго доказаны.

По теме диссертации были сделаны доклады на следующих научных семинарах:

— Научно-исследовательский семинар при механико-математическом факультете МГУ под руководством Н.П. Долбилина.

— Научно-исследовательский семинар при механико-математическом факультете МГУ под руководством Д.А. Шабанова.

— Научно-исследовательский семинар при Математическом институте им. В.А. Стеклова Российской академии наук под руководством С.В. Коня-гина и И.Д. Шкредова.

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

— The Second Russian-Hungarian Combinatorial Workshop, Будапешт, Венгрия, 26-29 июня 2018.

— "Экстремальная комбинаторика и дискретная геометрия", Майкоп, Россия, 20-23 декабря 2018.

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-31-90016.

Публикации

Результаты диссертации опубликованы в работах [D1]—[D5], представленных в конце списка литературы. Всего по теме опубликовано пять работ, из них — две в соавторстве. Все работы опубликованы в журналах из перечня ВАК, индексируются Scopus и Web of Science. Все результаты данной диссертации, включая результаты, опубликованные в совместных работах, были получены автором диссертации самостоятельно.

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

Настоящая диссертация состоит из введения, четырех глав, заключения. Полный объем диссертации составляет 98 страниц. Список литературы содержит 79 наименований.

Благодарности. Автор выражает глубокую признательность своему научному руководителю профессору Шабанову Дмитрию Александровичу и научному консультанту профессору Райгородскому Андрею Михайловичу за постановку задач и неоценимую поддержку в работе. Автор также признателен доктору физико-математических наук Жуковскому Максиму Евгеньевичу за исключительно полезные замечания.

Гл яв ^^

Асимптотическое исследование задачи о свойстве Вк однородного гиперграфа

В этой главе исследуется экстремальная проблема об отыскании минималь-

п

к2

п

у которого любой остовный подгиперграф с достаточно большой долей ребер к

Результаты главы опубликованы в работах [01], [02].

1.1 Основные определения и история задачи

Проблема Эрдеши ХиМнили является одной из центральных в теории раскрасок гиперграфов. Напомним основные определения.

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

п

2

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

Впервые данная задача была поставлена в работе П. Эрдеша и А. Хайнала

в 1961 году (см. [1]). Требуется найти величину m(n, r), равную минимально возможному числу ребер в n-однородном гиперграфе с хроматическим числом больше, чем r :

m(n,r) = min {|E| : H = (V, E) — n-однородный, x(H) > r} .

В случае, когда r = 2, данную величину принято обозначать через m(n). Сам П. Эрдеш (см. [46], [47]) с помощью простых вероятностных рассуждений получил следующие асимптотические оценки дляш(п) :

e ln 2

2n-1 ^ m(n) ^ n22n(1 + o(1)). (1.1)

В дальнейшем нижняя оценка, в отличие от верхней, была улучшена в

[ ], [ ]

ший на сегодняшний день результат принадлежит Я. Радхакришнану и А.

[]

ш(п) ^ (0.1)2пл/(1.2) V 1п п

Существует большое количество различных обобщений задачи Эрдеша-Хайнала (подробнее см. [48]). Одно из таких обобщений было предложено в работе Д.А. Шабанова (см. [2]). Пусть к — натуральное число. Будем называть раскраску вершин гиперграфа в г цветов к-правильной, если в каждом

к

с величиной ш(п, г) обозначим через Шк(п,г) минимально возможное число

кг тов. В случае, когда г = 2, обычно шк(п, 2) обозначают просто через шк(п). Говорят, что гиперграф Н = (V, Е) обладает свойством Вк, если существует такая раскраска множества V в два цвета, что в каждом ребре содержится

к

Применяя простые вероятностные соображения, для велпчннышк(п) можно получить следующую оценку, которая при к = 1 соответствует нижней оценке из (1.1):

2П-1

шк(п) ^ —, -, , ч .

2-^=0 Уз)

Д.А. Шабановым в работах [2], [3] было доказано, что если к = к(п) = о(п/ 1пп), то существует такая функция ^(п) > 0, зависящая только от вида

функции к(п), стремящаяся к 1 при п, стремящемся к бесконечности, что

е 1п2 0 2

п

тк(п) ^ ^п2^к-л~(п^(п)-

Помимо этого Д.А. Шабановым в [51] была получена следующая нижняя оценка величины тк (п) :

/ / п N 1/2 е-к/2 2п-к \

т ^Г—Т Щ) ^

при условии, что к = к(п) = 0(1п п). В случае же, когда к имеет порядок роста между 1п п и д/п, наилучшей нижней оценкой является результат Розовской (см. [52], [53]):

2п-1

тк(п) ^ 0.19п1/47П-1-. (1.5)

и-1/

Подгиперграф И' гиперграфа И = (V, Е) называется остовным, если множество его вершин — V, а множество Е' его ребер является подмножеством Е.

ние задачи Эрдеша-Хайнала. Введем величину тк,е(п), равную минимально-

п

любой остовный подгиперграф с |Е'| > (1 — £)|Е| не имеет к-правильпой раскраски. При £ = 0 имеем тк,е(п) = тк(п). И вообще, легко показать, что при £ < то&1(п) выполняется равенство тк,е(п) = тк (п).

Из определения видно, что £ лежит в пределах от 0 до 1. При £ = 0 свойство Вк,е эквивалентно Вк. Д.А. Шабановым (см. [3], [51]) показано, что при

к1

£>(£С) )21—п

о=0

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

В итоге получаем, что величина тк,е(п) имеет смысл лишь при

£

1 ,(£ • 21-п) . (1.6)

тк(п) =0

[ ], [ ]

ществуют такие константы с и С, с которыми при к < С 1п п справедливо

неравенство

n 22n 2—2k g—k

mt,(n) > c ■ e ■ — ■ /t 2 X2 ■ . (1-7)

Видно, что результат (1.7) является аналогом (1.4): он получен возведением (1.4) в квадрат и домножением на е.

1.2 Формулировка новых результатов

Первый результат данной главы улучшает нижние оценки величины mk (n) при k, имеющем порядок роста не более, чем n1/2—^/л/In n, 0 < ô < 1/2.

Теорема 1. Существует, такая положительная константа c1, что для любых n ^ 30 w k ^ 2, удовлетворяющих неравенству

к ^ ^

выполняется

( п \1/2 2п Шк(п) * СЧкгп^) • (1-9)

Вторым результатом первой главы является нижняя оценка для величины Шк,е(п). Она хуже, чем (1.7) при к ^ С 1пп. Однако, удается получить нетривиальную оценку в более широкой области значений к.

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

2к2(п - к) < (п - 2к)2,

выполняется

22\/п

mk,£(n) ^ c2 • -n-T-2 • е. (1.10)

u-i)

Третий результат главы улучшает результат (1.10) и оценку (1.7) Д.А. Шабанова при к, имеющем порядок роста не более, чем ni/2-¿/л/ln n, 0 < J < 1/2.

Теорема 3. Существуют такие положительные константы с3, с4, что для любых к ^ 2, м п ^ 30, удовлетворяющих условию

и любого

выполняется

к <

£ ^ сз тк,£(п) ^ С4

п 1п п

1

2п п 1п п'

22п

п

1п (п2к 1п п)

£.

(1.11)

(1.12)

На основании теорем сделаем выводы об асимптотическом поведении величины тк,е(п) при различных значениях к и £ и растущих к = к(п) и п. Пусть

Л (?) _ (к-!) 1п(п2к 1п п)'

£

С5 •

- с« • ._

п22п ' 2Ы пк 1п п

с5 с6

п \1/2 2п

тк,£(п) ^ С1

к 1п п

(п-1)'

Пусть

£

С6 •

(п-1) 1п(п2к 1п п)

-,С7 •

(п-1)

2пл/пк 1п п ' 2пл/к 1п п / '

с7

• Если к ^ \/п/ 1п п, то согласно теореме 3

22п

(1.13)

тк,£(п) ^ С4

п

(п-1)21п (п2к 1п п)

£.

£,

получаем следующую нижнюю оценку:

тк,£(п) = ^

2пп

(п-^ 1п(п2к 1п п)л/ к 1п п

Если >/п/ 1п п < к ^ О (\/п), Т0 согласно теореме 1

п \ 1/2 2п

тк,£(п) ^ С1

к 1п п

(к-1)'

Пусть

е е

/п-1\ / к—1

С7 •„ Л £ ("

2п\/ к 1п п:

п 3

2

1п

(1.14)

Если к ^ п/ 1п п, то согласно теореме 3

22п

тк,£(п) * С4

п

(п-1)21п (п2к 1п п)

е.

В частности, подставив нижнюю границу интервала (1.14) вместо е, мы получаем следующую нижнюю оценку:

Шк,е (п) = П , 1

2пп

(п:1) 1п(п2к 1п п) Если >/п/ 1п п < к ^ О (\/п), т0 согласно теореме 2

тк,£(п) * С2

22п

п

/п-1\2 к1

е.

е,

получаем следующую нижнюю оценку:

Шк,е(п) = П

п

(п-1)

п

1.3 Доказательство теоремы 1

Положим с1 равным 12/е26. Тогда для доказательства теоремы достаточно показать, что произвольный гиперграф, имеющий менее 12/е26 • (п/к 1п п)1/2 • 2п-1 /(к-!) Ребер, обладает свойством Вк.

Напомним и докажем некоторые вспомогательные факты. Пусть О = (Ж, Д) — произвольный гиперграф, а а — это некоторое биективное отображение Ж в {1, 2,..., |}, которое мы назовем нумерацией вершин гиперграфа О. Будем говорить, что пар а ребер (/, й) гипергра фа О образует упорядоченную 2-цепь относительно нумерации а, если выполнено |/ П = 1 и а(-и) ^ а (и) для всех V € /, и € й. Имеет место следующая лемма о связи обладания гиперграфом свойством В и наличия в нем упорядоченных 2-цепей, которая была предложена А. Плухаром в [54].

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

Далее мы рассмотрим критерий обладания гиперграфом свойством Вк, который является обобщением критерия А. Плухара и был впервые сформулирован А.П. Розовской в [52].

Для каждого ребра / € Е через Еа(/) обозначим множество первых к в нумерации а вершин ребра /, а через (/) обозначим множество последних к в нумерации а вершин.

Лемма 2. Пусть С = (Ж, Е) — произвольный гиперграф, каждое ребро

2к С Вк

а,

что для любых двух ребер / и в вы,полнено

и(/) П Еа(в) = 0. (1.15)

С свойством Вк, т.е. существует такая

раскраска его вершин в два цвета, что в каждом ребре содержится хотя бы к

образом: сначала пронумеруем все вершины первого цвета, а затем — второго. Легко проверить, что условие (/) П Еа(в) = 0 выполнено.

ак

а

к

вершин каждого цвета, т.е. гиперграф С обладает свойством Вк. Лемма доказана.

Итак, рассмотрим п-однородный гиперграф И = (V, Е), удовлетворяющий условию

12 / п \ 1/2 2п-1

|Е| = т < 16 ^ (Ч). (1.16)

1 1 е26 \к 1пп) (пк-1) 1 ;

Зададим случайную нумерацию на множестве V следующим образом. Каждой вершине V сопоставим случайную величину X, имеющую равномерное распределение па (0,1) .Номером а^) вершин ы V будем считать

аМ := Е I (X ^ } ,

где I — индикаторная функция. Пусть / € Е — ребро И. Для каждой вершины V € / введем события Е/(V) и Е/(V). Событие Е/(V) состоит в том, что

вершина V находится среди первых к вершин ребра /, а событие Д/ (V) — в том, что V находится среди последних к вершин ребра /. Для любых двух ребер / и й таких, что / П й = 0, и любой вершины v0 € / П й введем событие

М(/,^о) = Д/(vo) П ^о). (1.17)

Введем также событие М(/, й), равное объединению событий М(/, по всем вершинам v0 го пересечения ребер

М(/,й) = и М(/,^о).

«о€/пв

Итак, нам задана некоторая нумерация а множества V. Пусть / € Е — ребро Н. Без ограничения общности будем считать, что / = {1, 2,...,п} . Рассмотрим для каждой вершины v € / велич ину X и рас положим эти величины в порядке возрастания — получим ряд |Х(1),..., Х(п)} . Введем обозначения:

) = ^^(п—к+1),

ь(/ ) = Х(к).

Назовем ребро / "плотным", если

'(/) - И/) < ^,

где р положим равным 2к 1п п/п. Для каждого ребра / введем событие N(/),

/

М(/, й) := М(/, й) П!Щ/) П!Щз), М(/, й, Vo) := М(/, й, ПЙ/ П^, ^ := У N(/), Т := У М(/,5).

/€Е /,в€Е: /пв=0

Если нам удастся доказать, что сумма вероятностей событий ^ и Т строго 1, а

V, в которой для любых ребер / и й выполнено

Д(/) П ^(5) = 0,

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

Идея рассматривать лишь "плотные" ребра принадлежит Д.Д. Черкашину []

ство результата (1.2).

Далее мы оценим вероятности событий ^ и М(/, й).

1.3.1 Оценка вероятности события Я

Р (Я) = Р ^ N(/)J ^ |Е1шве Р (^(/)). Учитывая, что все вероятности N(/) одинаковые, получаем

Р (Я) ^ |Е|Р £(/) - Ь(/) ^

1 - р

= |Е| [р (С(/) ^ 1уР) + Р (*(/) - 6(/) ^ ^-, С(/) > ^-'

= |Е| Р («(/) < Т-—+

+ |Е| Р (с/) - Ь(/) < , «(/) > 1-^ . (1.18)

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

|Е|р(«/) <Ч) = 1ЕКп -1

1 -р 2

хп-к(1 - х)к-^х =

к1

= |Е |п

п1

+

к-1 к-1 ,

х

п-к+1

(1 - х)

к1

п — к + 1

1-р

+

1-р 2

п — к + 1

= |Е |п I

п1

х

п-к+1

(1 - х)

х

к1

п-к+1

(1 - х)к-2^х I =

к - 1 п - к + 1

к - 1 к - 2 п — к + 1п — к + 2

1-р

к — 1 х

п-к+2

(1 - х)

к2

п — к + 1 п — к + 2

1-р

+

1-р 2

х

п-к+2

(1 - х)к-3^х | = ... =

= |Е |п

п-1 к1

х

п-к+1

(1 - х)

к1

п - к + 1 +... +

1-р

+

к1

х

п-к+2

(1 - х)

к2

п — к + 1 п — к + 2

1-р

+

к1

к2

1 хп

п—к+1п—к+2 п—1п

1-р'

0

+

0

0

0

0

0

= |Е,п/п - 14 /(¥)""+' (1 - ^1 + к - 1 (^к+2 +

1 1 \к - 1/ ^ п - к + 1 п - к + 1 п - к + 2

+ ... + к - 1 к - 2 .. Ш"' | . (1.19)

п-к + 1п-к + 2 п-1 п '

Нетрудно проверить, что (1-)п-к+1 (1 - 1-р)к-1 к - 1 (1-)к-к+2 (1 - 1-)к-2

п-к + 1 п-к + 1 п-к + 2

к - 1 к - 2 1 (^)

*... *

п - к + 1 п - к + 2 п - 1 п Тогда за счет (1.16) выражение (1.19) оценивается сверху следующим обра-

зом:

(п - 14. (^)""+' (1 - V1 < 12 Г^ пк

|Е-1)к--< шп(1 -р) х

/1+ р\к-1 6 I п пк / 1пп2к\" / 2р 4 к-1

\ 1 - р) е26 у к 1ппп - к + 1 \ п у \ + 1 -р) <

6 пк 1 ( 2р(к - 1) 4 ^ ^ .

Здесь мы воспользовались неравенствами (1 - ")" < ехр(-х) и 1 + х < ехр (х) для х > -1. В силу того, что

( 2р(к - 1) \ ( 2рк \ / 2^к ехЧ^-г г ехри^)=ехр ^т-^п

= ех ( 4к21пп 4 < ех ( 4 (Л"")21пп ' =ех ( 4п \ ехНп - 2к 1пп^ < ех^п - 2у% 1пп ) ехР Vп - 2/ШппУ

/ , ^

= ехр

V1 - V ^

< ехр

< е13 для всех п * 30, (1.21)

1 2 /1п зо

^ - 2 у "зг/

получаем

6 I п пк 1 6 п3к2 ^

1 е13у к 1п пп - к + 1 п2к е13у к 1п п(п - к + 1)2п4к <

< А _ч/гпйп < А _1_<

< е13 у 1пп(п - ^/^пп)2п4к-33 < е13у 272(1пп)3/2п4к-7/2

6 1 1

< —,-< ,„ 1Ч для всех п ^ 30. (1.22)

27е13 V п 1п п 45е13 К ;

Теперь оценим второе слагаемое, стоящее в правой части (1.18).

| Е | Р («(/) - Ь(/) < Т-—^, «(/) > Ц■=

= 1 Е|п(п - 1) £ -(х-(1-(1 - = = ^|п(п - 1) Е С* - к) (^^/; (х - )' (1 - х)П-'^х =

=|Ет(п - 1)е (п-к)(^ Г-' к-г х

х/-р (х -Р) +1 (х - х)к-2^х=...=№(п -;; х

^ (п - к) (1-рГ-к-' (к - 1)! х

Х ¿Д г Л 2 ) Х (г + 1) • ... • (г + к - 1) Х х/¥(х - ^ ^ =

= |Е|п(п-1) Е -(рГ"(к-^ (х-1 -р41

к - 1 г \ 2 (г + к)! V 2

4 ' г=0 4 ' 4 ' \ / \ /

= |Е|п(п - 1)Ё (п-') Ц*

г+к

1 -р 2

Х (1 - Ч1) = . (1-23)

Оценим сумму по г в правой части (1.23). Для этого найдем в ней максимальное слагаемое, рассматривая отношение соседних слагаемых. Отношение слагаемых при гиг + 1 равно

/п-Ц ( 1+А %

р) (г + к + 1)(1 — р) г + к + 1

Список литературы диссертационного исследования кандидат наук Демидович Юрий Александрович, 2021 год

Список литературы

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

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

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

[4] P. Erdos, A. Renyi, "On random graphs I", Publicationes Mathematicae Debrecen, 6 (1959), 290-297.

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

[6] S. Janson, T. Luczak, A. Rucinski, "Random Graphs", Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.

[7] B. Bollobas, "Random graphs", Cambridge University Press, Cambridge, 2001.

[8] A. Frieze, M. Karonski, "Introduction to random graphs", Cambridge University Press, Cambridge, 2015.

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

[10] T. Luczak, "A note on the sharp concentration of the chromatic number of random graphs", Combinatorica, 11:3 (1991), 295-297.

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

[12] D. Achlioptas, С. Moore, "The asymptotic order of the random k-SAT threshold," The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., Vancouver, ВС, 2002, 779-788.

[13] A. Coja-Oghlan, L. Zdeborova, "The condensation transition in random hypergraph 2-coloring", Society for Industrial and Applied Mathematics, Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, 2012, 241-250.

[14] A. Coja-Oghlan, K. Panagiotou, "Catching the k-NAESAT threshold", Proc. 44th STOC (2012), 899-908.

[15] E. Shamir, J. Spencer, "Sharp concentration of the chromatic number on random graphs Combinatorica, 7:1 (1987), 121-129.

[16] N. Alon, M. Krivelevich, "The concentration of the chromatic number of random graphs", Combinatorica, 17:3 (1997), 303-313.

[17] A. Coja-Oghlan, K. Panagiotou, A. Steger, "On the chromatic number of random graphs", Journal of Combinatorial Theory, Series B, 98 (2008), 980993.

[18] A. D.N.J, de Grey, "The chromatic number of the plane is at least 5", Gcombinatories, 28 (2018), 5-18.

[19] A.M. Ри и городски и. "Хроматические числа", Москва: МЦНМО, 2003.

[20] О. Nechushtan, "On the space chromatic number", Discrete mathematics, 256:1-2 (2002), 499-507.

[21] D.A. Coulson, "15-colouring of 3-space omitting distance one", Discrete mathematics, 256:1-2 (2002), 83-90.

[22] A.M. Raigorodskii, "Combinatorial Geometry and Coding Theory", Fundamenta Informaticae, 145:3 (2016), 359-369.

[23] L.A. Szekely, "Erdos on unit distances and the Szemeredi-Trotter theorems", Janos Bolyai Mathematical Society, 11 2002. V. 11., P. 649-666.

[24] A.M. Raigorodskii, "Coloring Distance Graphs and Graphs of Diameters", Thirty Essays on Geometric Graph Theory., J. Pach ed., Springer, 2013, 429460.

[25] А. Я. Канель-Белов, В. А. Воронов, Д. Д. Черкашин, "О хроматическом числе плоскости", Алгебра и анализ, 29:5 (2017), 68-89.

[26] Л.И. Боголюбский, A.M. Райгородскнй, "Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками и £2", Математические заметки, 105:2 (2019), 187-213.

[27] Д.Д. Черкашин, A.M. Райгородский, "О хроматических числах пространств малой размерности", Доклады Академии наук, 472:1 (2017), 11-12.

[28] P. Frankl, R. Wilson, "Intersection theorems with geometric consequences". Combinatorica, 1 (1981), 357-368.

[29] A. M. Райгородский, "Проблема Борсука и хроматические числа некоторых метрических пространств", Успехи математических наук, 56:1(337) (2001), 107-146.

[30] A.M. Райгородский, "О хроматическом числе пространства", Успехи математических наук, 55:2 (2000), 147-148.

[31] D.G. Larman, С.A. Rogers, "The realization of distances within sets in Euclidean space", Mathematika, 19 (1972), 1-24.

[32] А. А. Сагдеев, "Об одной теореме Франкла-Уилсона", Пробл. передачи информ., 55:4 (2019), 86-106.

[33] R.L. Graham, B.L. Rothschild, and J.H. Spencer, "Ramsey theory", 2nd ed., Wiley Interscience, 1990.

[34] A. E. Звонарёв, A. M. Райгородский, Д. В. Самиров, А. А. Харламова, "О хроматическом числе пространства с запрещенным равносторонним треугольником", Математический сборник, 205:9 (2014), 97-120.

[35] А. Е. Звонарёв, А. М. Райгородский, "Улучшения теоремы Франкла-Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником", Труды МИ АН, 288 (2015), 109-119.

[36] М. Benda, М. Perles, "Colorings of metric spaces", Gcombinatorics, 9 (2000), 113-126.

[37] N.G. de Bruijn, P. Erdôs, "A colour problem for infinite graphs and a problem in the theory of relations", Nederland.se Akademie van Wetensehappen, Proceedings, Series A, 54:5 (1951), 371-373.

[38] P. Erdos, "Graph theory and probability", Canad. J. Math., 11 (1959), 34-38.

[39] P. Erdos, "Unsolved problems", Congressus numerantium, Utilitas Math., Winnipeg, 15 (1976), 678-696.

[40] N. Wormald, "A 4-chromatic graph with a special plane drawing", Journal of the Australian Mathematical Society Series A, 28:1 (1979), 1-8.

[41] R. Hochberg, P. O'Donnel, "Some 4-chromatic unit-distance graphs without small cycles", Geombinatoric, 5:4 (1996), 137-141.

[42] P. O'Donnell, "Arbitrary girth, 4-chromatic unit distance graphs in the plane.

I. Graph description", G combina tories, 9:3 (2000), 145-152.

[43] P. O'Donnell, "Arbitrary girth, 4-chromatic unit distance graphs in the plane

II. Graph description", G combina tories, 9:4 (2000), 180-193.

[44] E.E. Демёхин, A.M. Райгородский, О.И. Рубанов, "Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера", Математический сборник, 204:4 (2013), 4978.

[45] А.Б. Купавский, "Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами", Изв. РАН. Сер. матем., 78:1 (2014), 65-98.

[46] P. Erdos, "On a combinatorial problem", Nordisk Matematisk Tidskrift, 11 (1963), 5-10.

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

[48] A.V. Kostochka, "Color-critical graphs and hypergraphs with few edges: a survey", More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, Springer-Verlag, Berlin, 15 (2006), 175-197.

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

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

[51] Д.А. Шабанов, "Рандомизированные алгоритмы раскрасок гиперграфов", Математический сборник, 199:7 (2008), 139-160.

[52] А.П. Розовская, "Экстремальные комбинаторные задачи для двухцветных раскрасок гиперграфов", Математические заметки, 90:4 (2011), 584-598.

[53] А.П. Розовская, "О двухцветных раскрасках общего вида для равномерных гиперграфов", Доклады Академии Наук, 429:3 (2009), 309-311.

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

[55] D. Cherkashin, J. Kozik, "A note on random greedy coloring of uniform hypergraphs", Random Structures Algorithmщ 47:3 (2015), 407-413.

[56] С. McDiarmid, "On the chromatic number of random graphs",Random Structures and Algorithmщ 1:4, (1990), 435-442.

[57] К. Panagiotou, A. Steger, "A note on the chromatic number of a dense random graph", Discrete Mathematics, 309:10 , (2009), 3420-3423.

[58] N. Fountoulakis, R. Kang, C. McDiarmid, "The t-stability number of a random graph", Electronic Journal of Combinatorics, 17:1 , (2010), R59.

[59] A. Heckel, "The chromatic number of dense random graphs", Random Structures and Algorithmщ 53:3, (2018), 140-182.

[60] D. Achlioptas, A. Naor, "The two possible values of the chromatic number of a random graph", Annals of Ma,them,a,tics, 162:3 (2005), 1335-1351.

[61] A. Coja-Oghlan A., D. Vilenchik, "The Chromatic Number of Random Graphs for Most Average Degrees", International Mathematics Research Notices, 2016:19 (2015), 5801-5859.

[62] A. Coja-Oghlan, "Upper-bounding the k-colorability threshold by counting covers", Electronic Journal of Combinatorics, 20:3 (2013), Research paper №32.

[63] S.A. Kargaltsev, D.A. Shabanov, T.M. Shaikheeva, "Two values of the chromatic number of a sparse random graph", Acta Mathematica Universitatis Comenianae, 88:3 (2019), 849-854.

[64] J. Schmidt-Pruzan, E. Shamir, E. Upfal, "Random hypergraph coloring algorithms and the weak chromatic number", Journal of Graph Theory, 8, (1985), 347-362.

[65] E. Shamir, "Chromatic number of random hypergraphs and associated graphs", Advances in Computing Research, 5, (1989), 127-142.

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

[67] M. Dyer, A. Frieze, C. Greenhill, "On the chromatic number of a random hypergraph", Journal of Combinatorial Theory, Series B, 113 (2015), 68122.

[68] Д.А. Шабанов, "О концентрации хроматического числа случайного гиперграфа", Доклады Академии Наук, 475:1 (2017), 24-28.

[69] P. Ayre, A. Coja-Oghlan, С. Greenhill, "Hypergraph coloring up to condensation", Random Structures and Algorithms, 54:4 (2019), 615-652.

[70] H. Hadwiger, "Ungeloste Probleme", Elemente der Mathematik 11:16 (1961), 103-104.

[71] Р.И. Просанов, "Верхние оценки хроматических чисел евклидовых пространств с запрещенными рамсеевскими множествами", Математические заметки, 103:2 (2018), 248-257.

[72] Е.И. Пономаренко, A.M. Райгородский, "Новая нижняя оценка хроматического числа рационального пространства с одним и двумя запрещенными расстояниями", Математические заметки, 97:2 (2015), 255-261.

[73] A.M. Райгородский, "О хроматическом числе пространства с метрикой

Успехи, математических наук, 59:5(359) (2004), 161-162.

[74] N. Alon, J. Spencer, "The Probabilistic Method", 4th Edition, 2016.

[75] А.А. Сагдеев, "О нижних оценках хроматических чисел дистанционных графов с большим обхватом", Математические заметки, 101:3 (2017), 430-445.

[76] Р.И. Просанов, "Контрпримеры к гипотезе Борсука, имеющие большой обхват", Математические заметки, 105:6 (2019), 890-898.

[77] A.A Sagdeev, A.M. Raigorodskii, "On a Frankl-Wilson Theorem and Its Geometric Corollaries", Acta Math. Univ. Comenian. (N.S.), 88:3 (2019), 1029-1033.

[78] A.M. Ри и городским. "О дистанционных графах, имеющих большое хроматическое число, но не содержащих больших симплексов", Успехи математических наук, 62:6 (378) (2007), 187-188.

[79] A.M. Райгородский, "Линейно-алгебраический метод в комбинаторике", Москва: МЦНМО, 2007.

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

[D1] Ю.А. Демидович, "Некоторые обобщения задачи о свойстве В п-одно-родного гиперграфа," Фундаментальная и прикладная математика, 23:1 (2020), 95-122.

[D2] Ю.А. Демидович, A.M. Райгородский, "Двухцветные раскраски однородных гиперграфов", Математические заметки, 100:4 (2016), 623-626.

[D3] Ю.А. Демидович, Д.А. Шабанов, "О хроматических числах случайных гиперграфов", Доклады российской академии паук, Математика, информатика, процессы управления, 494 (2020), 30-34.

[D4] Ю.А. Демидович, "Нижняя оценка хроматического числа рационального пространства с метрикой с одним запрещенным расстоянием", Математические заметки, 102:4 (2017), 532-548.

[D5] Ю.А. Демидович, "Дистанционные графы в рациональном пространстве с большим хроматическим числом и без клик заданного размера", Математические заметки, 106:1 (2019), 24-39.