Раскраски би-однородных гиперграфов

«Московский физико-технический институт (национальный исследовательский университет)», 2021

1.2.    Математического ожидание и хроматическое число

Одним из классических примеров задачи теории раскрасок гиперграфов является задача Эрдеша-Хайнала о нахождении величины т(п), равной минимально возможному количеству ребер гиперграфа в классе п-однородных гиперграфов с хроматическим числом больше двух [5]. На сегодняшний день лучшими оценками величины т(п) являются оценка Радхакришнана-Сринивасана [9] С1^0|^2^п< т(п) и оценка Эрдеша [4] т(п) <  e¹'^² п²2^п.

Эрдеш и Ловас [6] заметили, что поиск величины т(п) связан с нахождением минимума функции / (Н ) = ^2_eGE 2^-п+1 по всем гиперграфам Н , у которых х(Н ) > 2.

В случае правильных двухцветных раскрасок неоднородных гиперграфов изучается функция J (Н ) = £_eGE 2^-|е|+1. Так, впервые Беку [1] удалось доказать, что если минимальный размер неоднородного гиперграфа Н хотя бы к и / (Н ) < Ө (log* к), то Н момсно правильно раскрасить в два цвета. В формулировке Бека [1] log* к обознает обратную функцию по отношению к функции 2 tt к (башня из к двоек). В 2008 году Лу аннонси-ровал доказательство оценки yOgofOge, но, к сожалению, в нем нашли ошибку. В 2018 году Дюрай, Гутовский и Козик [2] доказали оценку С log к, и на сегодняшний день она самая наилучшая из известных для общего случая. В частном случае для простых неоднородных гиперграфов известна оценка Vk, доказанная Шабановым [10].

Другим интересным направлением является получение верхних оценок для функции J(Н). Из результата Эрдеша [4] следует, что существует к-однородный гиперграф с х(Н) > 2. у которого математическое ожидание количества одноцветных ребер равно Ск2. Данную оценку пытались улучшить много лет, но пока никому не удалось. Некоторые исследователи выдвигали гопотезу, что данную оценку можно улучшить, если рассматри вать неоднородные гиперграфы. Однако на сегодняшний день пока таких результатов не известно. Дюрай, Козик и Шабанов [3] недавно показали, что случайный однородный гиперграф с числом ребер \Е| < (1 — е)e1n4(2) к22к почти наверное является 2-раскрашиваемым, т.е. имеет хроматическое число, равное двум. Среди явных конструкций гиперграфов, ко

торые нельзя правильно ракрасить в два цвета, известны оценка Гебауэр [7] 2к+ө(к^ / ) и впоследствии немного улучшенная на основе оценки Гебауэр оценка Гутовского, Дюрая и Козика [2] 2мө((к 1)1/2).

1.3.    Постановка задачи и наш результат

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

По аналогии с задачами из теории Рамсея, раскраску вершин би-однородного гиперграфа. Н = (V, Е1,Е2) мы решили называть рамхеевской. если нет красных ребер ііз Еі іі одновременно нет синих ребер из Е2. Для данного типа раскрасок нами получен следующий результат.

Теорема 1. Пусть Н = (К, Е^, Е_п) - би-однородный гиперграф с размерами ребер кип, соответственно. Пусть выполнено следующее соотношение:

ІЕІ +----1^Е„|     < log ^п .

2^к    2^п Vn( log³ п        log log п

Если 2 <  к <  log ^ _п , то для Н существует рамсеевская раскраска.

Следствие 2. Пусть Н = (V, Е^, Е_п) - би-однородный гиперграф, с размерами ребер к и - / 100 log log п 1    100 log п\ л

• п. соответственно, и пусть существует р Е (--- ^ ——, 1-- —^ ) • ^^ которого

Е | +        \Еп\

< logn.

р^к (1 — р)^п^п/ log² п

Если 2 <  к <  . ^п₂ , — log п¹

то для Н существует рамсеевская раскраска.

2.    Алгоритм раскраскиЭтап 1. Случайная раскраска

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

Рис. 1. Короткие красные е Е Е^ и синие / Е Е_п ребра в раскраске С1

Введем понятие «коротких ребер». Пусть р^ и р_п - некоторые функции, которые мы определим позже. Назовем ребро е Е Е^ (аналогично / Е Е_п) коротким, если все его вершины имеют вес меньше, чем 1/2 — р^ (больше, чем 1/2 + р_п). Назовем ребро е Е Е^ почти красным, если все, кроме может быть одной вершины, покрашены в красный цвет. Соответственно, красными из Е^ (синими из Е_п) ребрами мы называем е Е Е|_c(f Е Е_п") ребра, все вершины которых покрашены в красный (синий) цвет.

Этап 2. Перекраска красных ребер из Е^

Пусть Г1,«2. ..,и_т - вершины гиперграфа, записанные в порядке ст, т.е. ст(щ) <  ст(^2 ) < ... <  ст(и_т). Мы перебираем вершины, начиная с щ, и если текущая вершина, назовем ее н_сиг, лежит в одноцветном в текущей раскраске красном ребре е Е Е^. все остальные вершины которого имеют вес меньше, нем ст(и_спг ), то перекрашиваем и_сит в синий цвет и переходим к следующей вершине. Ребро е, из-за которого была перекрашена и_сиг, будем называть при чиной для перекраски и_сиг. Обозначим раскраску, получившуюся после этапа 2, через С2.

Этап 3. Перекраска синих ребер из Е_п

В каждом синем ребре е Е Е_п перекрашиваем в красный из неперекрашенных на этапе 2 самую легкую из вершин.

Рис. 2. Красное в раскраске С3 ребро е Е Е^ и ребро / Е Е^, которое стало причиной для перекраски самой тяжелой из перекрашенных вершин в е

Далее мы опишем конструкцию, которая была предложена Гутовским, Дюраем и Козиком в их совместной работе [2]. В дальнейшем данная конструкция позволит нам оценить вероятность появления одноцветных синих ребер.

3.    Вспомогательный гиперграф

Утверждение 1. Пусть на втором этапе алгоритма оказалось так, что |f П е| > 1 и ребро е является причиной для перекраски некоторой вершины Е f П е. Тогда f Е Е_п никогда не станет синим.

Доказательство. Согласно алгоритму, н является самой тяжелой вершиной в ребре е. Пусть w - любая другая вершина п:з пересечения f П е. Тогда если ребро f стало сипим, то w должна была перекраситься в сшшй раньше, нем н. но в таком случае ребро е не может быть причиной для перекраски н. Противоречие. □

Вспомогательный гиперграф. Утверждение 3 позволяет нам рассмотреть следующую конструкцию. Для каждого ребра f Е Е_п определим (к — 1)-однородный гиперграф Hf на множестве вершин V\f. Для каждого ребра е Е Е^, имеющего ровно одну общую вершину с f (т. е. |f П е| = 1), мы кладем cj = е \ (f П е). Таким образом, мы определяем набор ребер Hf как мікжество {еf : е Е Е^ , |f П е| = 1}. Поеко.твку еf может совпадать с еf. для разных ребер е и е‘, то Hf является мультигиперграфом.

Обратим внимание, что всякий раз когда мы фиксируем цвета вершин в Hf, предполагая, что ребро f стало синим в раскраске С2, то в ребре f мы можем однозначно выбрать множество вершин, которые заведомо были синими в изначальной раскраске С1. Почему так?

Назовем вершину н Е f опасной для ребра f, если существует еf Е Hf : (еf U н) Е Е^ и еf красного тщета. Только опасные вершины могли не быть сшшмп в раскраске С1.

Для каждого ребра f будем обозначать множеств о его опасных вершин через Ef.

4.    Доказательство Теоремы 1

Пусть H = (V,Еk,Е_п) - бн-однородный гиперграф. с |Е^| = 5е& 2^к 11 |Е_п| = 5 е_п2^п. Значение е& 11 е_п будет определено позже, пока лишь будем требовать, чтобы к • ^log ^^{£ n} < log-². Применим к H Алгоритм из раздела 2 с р^ = log^ ^и Р_п = log, | ⁿ • Несложно посчитать, что математическое ожидание почти красных ребер не превосходит ^й Далее заметим, что с вероятностью не меньше, чем 5 в случайной равномерной раскраске не будет коротких ребер и почти красных ребер будет не больше, чем ^й Далее будем рассматривать только такие исходы.

Предположим, что алгоритм не сработал. Несложно проверить, что в этом случае на этапе 3 должны были появиться красные ребра из Е^. Пусть е - одно из таких ребер. Согласно алгоритму, в ребре е есть перекрашенные на этапе 2 вершины, выберем среди них самую тяжелую вершину, вершину н. Для данной вершины н возьмем синее в раскраске С2 ребро f Е Е_п. которое стало причішой для перекраски н. Назовем так}то пар}’ ребер (е, f ) опасной. Рассмотрим гиперграф Hf. Зафиксируем некоторую раскраску Hf. Как только мы зафиксировали раскраску, мы можем определить опасные и не опасные вершины в ребре f. что позволяет нам оценить ус.тови}то вероятность того, что пара ребер (е, f ) опасная при условии, что количество опасных вершин в ребре f ровно г и ст(н) = у:

( 2+<1 ( 1Д у-¹ ( 2+ ^р. у и

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

P((e,/) опасна я параду | = т)

<    2^+ⁿ-2

r log еу log e„ • e n•2„+к-2 ’

где в конце мы воспользовались тем, что 2кр„ < log2.

Количество опасных вершин не может быть больше, чем количество почти красных ребер, имеющих с ребром / ровно одну вер шину. Отсюда, E|^f | < еу. С другой стороны, мы установили, что с большой вероятностью всех почти красных ребер, не только которые пересекаются с ребром J, не больше, чем ^^. Поэтому для перехода от условной вероятности к безусловной достаточно просуммировать по всем т < ^ф. Итак, r log еу

P((e,J) опасная пара) = ^ 1 og^”^к-2  • P(I^fI = т) < т< o • e (үҮ ү'

где

₌^f I log ^ек к

•2„+к-2     V2 у ,

Математическое ожидание е^ү может быть оценено в силу выпуклости функции экспоненты и условия, что EY = log ^E¹^I< ^ek log ^j_k , о_{кончательно} получаем, что

P^{(e Е}Ек красное)  <  £ _n ^^

f ЕЕп

' Р g у }   <   e„loge„ -p ' g^

к         ~   2п • 2^k-2      к

Подставляя ek = loogo^ 11 e„

iog„„, мы получаем, что искомая вероятность в (2)

1    __________ ______ ___ _________ „ „   _____________„„ меньше, чем 5^।, следовательно, с положительной вероятностью существует рамсеевская раскраска. Теорема 1 доказана.

Поскольку мы могли красить на этапе 1 необязательно равномерно, то константа 1/2 может быть заменена на любое р Е (0,1). Также правая часть в Теореме 1 может быть улучшена до logn. Таким образом, имеет место быть следующее утверждение, которое мы приводим здесь без доказательства.

Следствие 3. Пусть Н = (У,Ек, Е„) - би-однородный гиперграф, с размерами ребер к и /100 log log „ 1    100 log „\ □ n соотостстгоснно. и пусть суи^сслтзуст р Е (----к , 1--/; )• ^-^ которого:

|Ек| +          |Е„|

< logn.

р^к (1 — р^СС log²n

Если 2 < к < iog„ „, то для Н существует рамсеевская раскраска.

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 20-31-90029. Автор является победителем конкурса «Молодая математика России» и выражает благодарность его спонсорам и жюри.