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

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

Один из базовых фактов теории графов состоит в том, что для любого графа G выполнено

_X(G) 6 A(G) + 1.

Однако, как показали Хайнал и Семереди [1], в данных условиях имеет место более сильное утверждение, а именно, что каждый граф G можно справедливо раскрасить в A(G) + 1 цвет. Напомним, что раскраска, называется справедливой, если она является правильной и мощности всех цветовых классов отличаются не более чем на. единицу. Настоящая работа, посвящена, обобщению теоремы Хайнала-Семереди на. случай гиперграфов.

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

а(н) 6 Г2_1, еп то Х(Н) 6 г. Данный результат был обобщен на случай справедливых раскрасок в работе Лу и Секеи [3]. Они показали, что если число вершин п-однородного гиперграфа Н делится на. г II

А(Н) 6

_г П - 1

2еп ’

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

Для класса простых гиперграфов, т.е. гиперграфов, у которых любые два различных ребра имеют не более одной общей вершины, результат Лу и Секеи был усилен в работе Шабанова [4], где было показано, что если Н - простой п-однородный гиперграф с

А(Н) 6 с

2П-1

V п 1п п

где с >  0 - некоторая абсолютная константа, то для Н существует справедливая раскраска в два цвета.

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

Теорема 1. Существуют такие п₀ Е N и с > 0, что при п > п₀ для любого п-однородного простого гиперграфа Н = (V, Е ) с максимальной степенью вершины, не превосходящей с • 2^П-1, существует справедливая раскраска Н в два цвета.

Отметим, что для случая обычных раскрасок (а не справедливых) данный результат был получен ранее в работе Козика и Шабанова [5]. Найденная в теореме 1 оценка на максимальную степень вершины достаточно близка к максимально возможной, так, например, в работе Косточки и Рёдля [6] было доказано существование простых гиперграфов с хроматическим числом больше двух и максимальной степенью вершины не более \п2^п-1 1п2ф В следующем разделе мы приведем доказательство теоремы 1.

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

• 2.1.    Алгоритм перекраски

Пусть |V| = N. Без ограничения общности можно считать, что N четно, иначе можно добавить одну изолированную вершину. Рассмотрим W и В — два непересекающихся множества размера N/2. Нам необходимо показать, что существует справедливая раскраска Н в два цвета, т.е. что существует такая биекция f: V ^ W U В, что для любого ребра А Е Е выполнено f (А) £ W и f (А) £ В.

Мы построим некоторую случайную биекцию и покажем, что с положительной вероятностью она будет удовлетворять искомому свойству.

Для построения случайной биекции мы воспользуемся методом случайной перекраски, следуя идеям из работ [5], [4]. Суть его проста: если некоторая раскраска не является искомой, то мы случайной перекраской небольшого числа вершин пытаемся ее исправить.

Рассмотрим случайную биекцию то : V ^ W UB, имеющую равномерное распределение на множестве всех биекций. Будем говорить, что вершина и Е V имеет начальный белый

(черный) цвет, если то(г) G W (В). Кроме того, пусть для каждой вершины г задана случайная величина Х_ц, имеющая равномерное распределение на [0; 1] и независимая как с то, так и с остальными случайными величинами X_u,ti G V \ {г}. Вели чину Х_ц будем называть весом вершины г, и будем называть вершину свободной, если ее вес не превосходит некоторого числа р G (0,1/2), которое является параметром нашей конструкции.

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

• •    Т (г) = т- 1 (ст(т о (г))). если т о (г) G W:

• •    Т (г) = т₀-¹(ст^-1(т о (г))). иначе.

Случайную вершину Т (г) будем называть двойственной к вершине г. Заметим, что начальные цвета двойственных вершин всегда различны по построению.

Опишем следующий алгоритм изменения биекции т о (и индуцированной ею раскраски):

• 1)    На вход алгоритм получает начальную раскраску, веса всех вершин и разбиение на двойственные пары.

• 2)    Если в текущей раскраске т индуцированной текущей биекцией есть одноцветное ребро А, то находим в этом ребре свободную вершину г с наименьшим весом, которая еще ни разу не была перекрашена.

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

^т г+1 ^{(г) :}= ^т г ^{( Т (г))};

^т г+1 ^{( Т (г)) :}= ^т г ^(г);

т_г +1 (п) := т_г(п) для л тобой n G V \ {г,Т (г)}.

• 4)    Повторяем второй шаг пока возможно.

• 2.2.    Построение ^-дерева

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

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

• 1 ) либо вершина г G А была изначально белой и несвободной,

• 2 ) либо вершина г G А была изначально черной, свободной и перекрашена в процессе работы алгоритма.

Рассмотрим подробнее вершины второго типа. Если вершина г сменила свой цвет, то снова возможны две ситуации:

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

• ( б) либо двойственную вершину Т (v) содержало не которое ребро С, которое в некоторый момент процесса перекраски оказалось полностью белым и Т (v) была свободной вершиной с наименьшим весом среди еще неперекрашенных.

В первой ситуации будем говорить, что ребро В портит вершину v, а во второй - что ребро С портит вершину Т (v). Далее, само ребро В не обязано было быть изначально полностью черным, значит, в нем могли быть изначально белые вершины. Раз в какой-то момент процесса перекраски оно оказалось полностью черным, то для каждой подобной вершины было ребро, которое ее испортило.

Данное рассуждение показывает, что можно рассмотреть следующую конфигурацию, которую мы будем называть ^-деревом:

• •    R = (V‘,Е‘) - граф-дерево с корнем, вершинами которого являются ребра исходного пшерграфа. Н

• •    корень - это ребро А;

• •    пара, ребер (А, В') пшерграфа сое,тнияетвя ребром е в дереве R. если в ребре А либо нашлась вершина v, которую испортило ребро В ' (тогда ребро е будем называть настоящим) , либо нашлась вершина v такая, что ребро В' испортило двойственную вершину Т (v) (тогда ребро е будем называть мнимым)',

• •    в предыдущем случае будем говорить, что ребро В' является потомком ребра А в дереве R, тем самым, каждой вершине из А может соответствовать не более одного потомка;

• •    если ребро А в процессе перекраски стало полностью одноцветным тщета а(А'). то будем говорить, что цвет а(А') является доминирующим в ребре А';

• •    дерево R является полным, т.е. множество потомков А в дереве R в точности соответствует множеству вершин А, имевших изначально не доминирующий цвет а(А').

• 2.3.    Случай 1: ребро с большим числом потомков

Заметим, что наличие одноцветного ребра А в итоговой раскраске влечет наличие полного ^-дерева с корнем А. Остается разобрать различные варианты структуры ^-дерева.

Пусть ребро А в дереве R имело хотя бы п/3 потомков. Это в точности означает, что в нем было не менее п/3 вершин, каждая из которых либо сама была свободной, либо свободной была ее двойственная. Заметим, что А не может содержать пару двойствен ных вершин, в противном случае оно не могло стать одноцветным в процессе перекраски. Обозначим данное событие через В(А). Тогда вероятность события В(А) оценивается следующим образом:

Р(В(А')) 6

('з '

6 2 2n _p nJ3

Для применения локальной леммы нам понадобятся локальные полиномы для всех видов событий. Для событий типа В он будет выглядеть следующим образом: Vv Е V w1(z) = ^ Р(В(А')) • z^'1 6 22>п/3 • А(Н) • zn.                (2.1)

A'wEA'

• 2.4.    Случай 2: гипердерево

Пусть R - это полное ^-дерево с корнем А и любая вершина ^-дерева имеет не более п/3 потомков. Осуществим следующую процедуру над множеством вершин исходного гиперграфа: отождествим двойственные вершины. Если после применения подобной процедуры набор вершин К-дерева как набор ребер гиперграфа Н образует настоящее гипердерево, то будем называть такой случай правильным К-деревом.

Выделим следующие свойства правильного К-дерева:

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

• •    если R состоит из т вершин и имеет и мнимых ребер, то число вершин Н, входящих в R, равно т • (п — 1) + 1 + и и среди них будет и двойственных пар;

• •    для каждого ребра А’, не являющегося корнем R, существует вершина г € А’, которую А’ испортило, тог да эта вершина г будет иметь наименьший вес среди всех вершин А’, не соответствующих потомкам А’. Все подобные подмножества вершин не будут попарно пересекаться и будут иметь мощность не менее 2п/3;

• •    все вершины А, которые не соответствуют его потомкам, являются несвободными.

Обозначим выражение N !/(N — т)! как (N)_т Тогда вероятность начальной раскраски вершин R при фиксированном итоговом цвете корня А равна

(N/2L V 2 — «)т.(ң-1)+1-а

(N )т^(п-1)+1+и где а - число белых вершин в К-дереве. Теперь оценим это выражение. Обозначим q = т • (п — 1) + 1, тогда

(N/2X (N/2 — u)_q__a

(N )q+u

_—q N(N — 2)... (N — 2а + 2)(N — 2и) ... (N — 2и — 2q + 2а + 2)

=                   N(N — 1)... (N — q — и + 1)               .

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

Если и >  а, то тогда правая часть (2.2) не превосходит

_—q (N — 2и)... (N — 2и — 2q + 2а + 2) (N — 1)(N — 3)... (N — 2а + 1) ^Х

(N — 2а)... (N — а — и + 1)(N — а — и) ... (N — q — и + 1) (заметим, что (N — 2и) ... (N — 2и — 2q + 2а + 2) 6 (N — а — и) ... (N — q — и + 1))

6 2^—q--------------

6    (N — 1)(N — 3)

(N — 2а + 1)(N — 2а) ... (N — а — и + 1) 6

6 2—q

(N — 1)(N — 3)... (N — 2и + 1).

Если же а > и, то правая часть (2.2) не превосходит

_—q            (N — 2и)... (N — 2и — 2q + 2а + 2)

(N — 1)(N — 3)... (N — 2а + 1)(N — 2а)... (N — q — и + 1)^.

Множитель (N — 2и + 1) находится перед (N — 2а + 1), и, начиная с него в знаменателе, множители последовательно уменьшаются сначала на 2, а потом, дойдя до (N — 2а), — на 1, при этом общее число множителей равно q — а + 1. Стало быть, числитель меньше подобного хвоста знаменателя даже без последнего множителя (N — q — и + 1). Отсюда оцениваемое выражение не превосходит

2—q

(N — 1) ••• (N — 2и + 3)(N — q — и + 1) ’ что несколько больше, чем полученное выражение в предыдущем случае, когда п > а. Заметим далее, что п 6 m 6 q/(n — 1) < N/4 пр и п > 5. Таким образом, вероятность не превосходит

2 ^v (2/N ) ^{u- 1} (N — q — п + 1)^-1.

Обозначим через НТ (R) рассматриваемое событие, когда R является правильным полным h-деревом. Тогда, в силу предыдущих рассуждений, мы получаем, что

/ 3 \ т-1

Р(НТ(R)) 6 2- (2/N)^U-1(N — q — п + 1)^-1 J — \    (1 — р)^^п/3.

Далее, для каждой вершины v оценим локальный полином, отвечающий событиям НТ (R), когда v G R:

-            52    Р(НТ(R)) • 2^{2 | v (R)|},

R : v E V (R)

где V (R) - множество вершин ii сходного гішерграфа в h-дереве R.

Вспоминая, что q = m • (п — 1) + 1, получаем, что

w 2 (_Z) =    52    2 '' (2/N )^U-1(N

R : v E V (R)

—

q — п + 1)^-1 • () '     (1 — ,     3 •     ⁺   =

1 Е(Н ) | т - 1

= Е Е т4 ”

т=1 и=0

(^m 1)д(Н)(пД(Н))^т-1

-

U(NnД(Н ))их

_x2^-(m^⁽n^-1)+¹⁾(2/N)^U-1(N — m • (п — 1) — п)^-1 • ( 1^ ) (1 — р)^2п/3 • з²'"^" ''■^+і . (2.3) Прокомментируем полученное неравенство. Сколько h-деревьев размера men мнимыми ребрами может содержать фиксированную вершину v? Необходимо выбрать

• •    структуру дерева (не более 4^т способов),

• •    номер ребра, которое будет содержать v (не более m способов),

• •    номера мнимых ребер ((^т—1) способов),

• •    ребро, содержащее v (не более Д(Н) способов),

• •    последовательно остальные ребра конфигурации (не более (пД(Н))^m-1-U(NnД(Н))^и способов, ведь при настоящем переходе мы выбираем ребро, содержащую вершину из уже имеющего ребра, не более пД(Н ) способов, а при мнимом — вершину из имеющегося ребра, любую другую в качестве двойственной и ребро, содержащее двойственную, не более чем пД(Н )N способов).

• 2.5.    Случай 3: большое поддерево

Пусть теперь при отождествлении двойственных вершин полного h-дерева R мы не получили настоящее гипердерево, а получили конфигурацию ребер, содержащую циклы. Для каждой вершины В h-дерева введем понятие полного h-noddepeea с корнем в В, состоящего из всех вершин h-дерева, чей кратчайший путь до корня проходит через В. Рассмотрим S - минимальное по размеру полное h-поддерево R, которое при отождествлении двойственных вершин содержит цикл из ребер гиперграфа Н. Тогда каждое поддерево самого S уже не содержит циклов и возможны две ситуации:

• 2)    либо нашлось поддерево S' с корнем В' размер а более ln п.

В данном параграфе мы разберем второй случай.

Заметим, что S' очень похоже на правильное ^-дерево. Единственное отличие состоит в том, что про вершины В ', которые не соответствуют его потомкам в S', мы не можем сказать, что они являются несвободными вершинами. Тогда, обозначая это событие через HS (S'), получаем, что его вероятность не превосходит

P(HS(S')) 6 2^—9(2/N )^U—1(N — q — n + 1)^—1

(-

т — 1

Далее, для каждой вершины г оценим локальный полином, отвечающий событиям HS(S) когда г Е S

w 3 (z) =    ^     P(HS (S')) • z^2|V(S‘ ) |,

S ’ : 4)EV (S ’ )

где V(S') - множество вершин исходного гішерграфа в ^-поддереве S'. Вспоминая, что q = т • (п — 1) + 1. получаем, что w3(z)=   £   2 '' (2/N)и—1(N — q — n + 1)—1 • (Г 1 • z2(^ =

S ’ : b E V (S ’ )

т — 1

Е Е т4т т>1п п и=0

т — 1

n

А(Н )(пА(Н))т—1—u(NnA(H))их

х2 '^/т-^п ■'' (2 N)^и— 1 (N -т • (п — 1) — n)^—1

■( О

т — 1

• z 2(т • (n — 1)+1+и)

(2.4)

• 2.6.    Случай 4: короткие циклы длины > 2

Осталось рассмотреть случай, когда исходное ^-дерево при отождествлении двойственных вершин содержит цикл длины от 2 до 21пп + 1 из ребер гиперграфа Н. Случай циклов длины 2 - особый, и мы разберем его позднее. Пусть теперь С = (А1,..., А_т) - это простой цикл длины т >  3, получившийся в результате отождествления двойственных вершин, т.е. ребро А г ,г = 1,...,т, либо имеет одну общую вершину с ребром А_і+1, либо оно содержит вершину щ, двойственная к которой лежит в ребре А^₊ 1 (считаем, что А_т+ 1 = А 1).

Обозначим через а цвет, в котором ребро А ^ стало одноцветным в процессе перекраски. Тогда каждая вершина ребра А ^ либо имела изначальный цвет ад либо имела противоположный начальный цвет, но была свободной или же свободной была ее двойственная. Обозначим через n количество таких г, что г Е А^ и Т (гД Е А^дд Важное замечание состоит в том, что каждая вершина, не лежащая в пересечении ребер Ад не является двойственной ни к какой другой вершине нашего цикла. Обозначим через а количество изначально черных вершин цикла С, а через b - количество изначально белых вершин. В цикле имеется ровно n пар двойственных вершин, стало быть, вероятность подобного исхода равна.

( А ) ••• ( А ^{—а +} 1)( А ^{— n} ) • • • ( А ^{— b +} 1)

N(N — 1) ••• (N — а — b + 1)       .

Далее, а + b = т(п — 1) + n п n 6 т 6 21пп + 1. 'значит, величина, а + b не превосходит п². что сильно меньше, нем общее число вершин N. Следовательно, при больших п можно считать, что эта вероятность не превосходит

⁽ N ^{) а} +Ь - и

2 У 2 /   2 1 — ( п— 1) т n - ^и N ^а+^   ^—              .

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

(1 + 2р)^тп

• 2і—(п—1)mN—и

(2.5)

Множитель (1 + 2р)тп отвечает грубой оценке сверху для перебора вариантов: либо начальный цвет уже правильный, либо вершина свободная, либо свободной является ей двойственная.

Обозначим за С(С ) событие, состоящее в том, что С = (А_і,..., А_т ) образует простой цикл. Тогда в силу предыдущих рассуждений мы получаем, что

Р(С (С )) 6 (1 + 2р)^тп • 2^1-(n-1)mN^—и.

Далее, для каждой вершины г оценим локальный полином, отвечающий событиям С (С ), когда г Е С:

w 4 (.) =    £    Р(С (С )) • ^^{( С})1

С : dEV (С)

где У (С ) - множество вершин исходного гиперграфа в цикле С. Теперь

» 40 ) =  £  (1 + 2Д^т "

С : d E V (С)

2 І — (п — 1)т n — и ^ 2(п — і)т+и

т/ \

=  ££”С)

36т621п п+1 и=0' '

(А(Н))^m—1п^mN^u • (1 + 2р)^тп

2 І — (п - 1)m N— и ^ 2((п — 1)т+и)

(2.6)

Поясним последнюю формулу. Ребро А г цикла С, содержащее вершину г, можно выбрать А(Н) способами. При уже выбранном ребре A j верш ину г^, участвующую в пересечении ребер A j и A j+i, можно выбрать не более чем п способами, двойственную к ней - не более чем N способааш (это необходимо сделать и раз), а само ребро A j+ ₁ - не бо.дее. чем А(Н ) способами. Наконец, последнее ребро А г - і можно будет выбрать не более одного способа предварительно выбрав вершину гг_—і в ребре А г (и двойственную к ней при необходимости).

• 2.7.    Случай 5: короткий цикл длины 2

Рассмотрим случай, когда исходное ^-дерево при отождествлении двойственных вершин содержит цикл длины ровно 2 из ребер гиперграфа Н. Пусть теперь D = (Аі, А2) — это подобный 2-цикл. Заметим, что в силу простоты гиперграфа Н ребра Аі, А2 не могут иметь более одной общей вершины, поэтому все оставшиеся совпавшие в результате отождествления вершины являются парами двойственных вершин. Обозначим через и количество пар двойственных вершин в ребрах Аі, А2 и через s - количество общих вершин Аі, А2. Тогда s Е {0,1}. а и >  2 — s.

Теперь воспользуемся оценкой вероятности (2.5), которая верна и для 2-цикла. Обозначим изучаемое событие через 8С (D), тогда

Р(5С(D)) 6 (1 + 2р)^2п • 2^1+s—‘^2пN^—и.

Осталось для каждой вершины г оценить локальный полином, отвечающий событиям 8С (D). ко гда. г Е D;

^) =    £ Р^С(D)) • 2^{2 | v (D)|},

D : dEV (D)

где У(D) - множество вершин исходного гиперграфа в 2-тщкле D. Теперь w5(z) =   £ (1 + 2р)2п • 21+s—2пN—ид4п =

D : dEV ( D )

1 п— S

= ^ ^ 2А(Н >^s(nN)^2—s(1 + 2p)²ⁿ • 2^{1+s— 2n}N^—uz⁴ⁿ.            (2.7)

Поясним последнюю формулу. Ребро Аг, содержащее вершину v, можно выбрать А(Н ) способами. В выбранном ребре Аг надо выбрать либо одну общую вершину с ребром Аз-г и вторую с ней двойственную, либо две пары двойственных вершин. В обоих случаях само ребро Аз- і можно выбрать не более чем одним способом в силу простоты гиперграфа.

• 3.    Локальная лемма

Для завершения доказательства теоремы нам понадобится специальный случай локальной леммы. Сформулируем ее в удобном для нас варианте.

Лемма 1. Пусть А1, ..., Ам - это события на вероятностном пространстве. Пусть для каэюдого события А_г выделено некоторое конечное мнолсество dom(Аг) с таким условием, что для любого J С {j: d^m(Аj ) П дот(А_г) = 0} выполнено

P I Аг | Q А I 6 Р(А).

(3.1)

jeJ

м

Обозначим через DOM = U dom(Аг) и для каэюдого v Е DOM введем полином г=1

U (z) =    ^   Р(Аг )z^ldom(AiK

г : nEdom^Ai)

Если существует такой полином u(z) с условием u(z) > и (z) для любых v Е DOM и z >  1. a mtікэісс у Е (0,1). такое, что и(1/(1 — у)) 6 у. то

Р '

> 0.

Для исходной случайной биекции t q и произвольного набора вершин U нашего гиперграфа. Н можно рассмотреть катоническое событие' A(U,Q,g) где Q С W U В. |Q| = |U|. g : U т Q - фиксированная биекция, состоящее в том, что

A(U, Q, д') = {Vv Е U tq(v) = g(v)}.

Два канонических события A(U, Q,g) и A(U‘,Q‘,g‘) конфликтуют, если 3v EU nU ‘: g(v) = g‘(v) ил и 35 e Q П Q‘: g^—1(5) = g^,—1(5).

Из работы Л у и Секеи [3] известно, что свойство отрицательной корреляции (3.1) выполнено для канонических событий, если для любого j Е J событие Аj не конфликтует с событием Аг-

Каждое плохое событие из SC (D) С (С ), HS(S) НТ (И), D(А') можно представить как дизъюнктное объединение простых событий вида L = A(U, Q,g) П {(Уу ,v EU ) Е F }, где U - это набор вершин пшерграфа. Н (плохая конфигурация). Q С W U В. A(U,Q,g) - каноническое событие, a F - некоторое борелевское множество. Для каждого такого события введем dom(L) = U U Q. Тогда, как было показано в работе [4] (утверждение 1 на с. 194), подобные события будут удовлетворять свойству (3.1). Все, что нам остается сделать, это оценить полиномы w_y(z) и подобрать значения параметров у, р, с, чтобы выполнялось неравенство и(1/(1 — у)) 6 У ДДЯ мажорирующего многочлена w(z).

Заметим, что в рассматриваемой нами ситуации DOM = V U W U В и для любого простого события L = A(U, Q, g) П{(Ау ,v Е U ) E F } выполнено |dom(L)| = |U| + |Q| = 2|U|.

Для каждой v Е V введем общий полином плохих событий, содержащих v:

W v (г) = Е ™. (г) = Е    P(L)гl^dom < ^L ’ l.

г =1            L:v E dom(L)

Для каждого из полиномов шЦ(г) были получены оценки (2.1), (2.3), (2.4), (2.6), (2.7), сумма которых и может выступить в качестве мажорирующего полинома w(z).

Если же v Е W UB, то общий полином плохих событий можно оценить следующим образом:

ш . (г) =   ^Е   p(L)z^Idom(L ’ ¹ 6 ^{е е}    P(L,t ₀ (q)= v)z\^dom(LK

L:v E dom(L)

q E V L:q,v E dom(L)

Вероятность события P(L,to (q) = v) оценивается точно так же, как и вероятность для выбранного плохого события L, единственное — мы требуем дополнительно, чтобы конкретная вершина q при случайной биекции перешла в конкретную вершину v. Это означает, что при суммировании вероятности для v не будет выбора из N/2 вершин. Следовательно,

™. (г) 6 ^{Е Е}    P(^LMq) = v)z^|dom(L)| 6

q E V L-.q,v E dom(L')

6 NN Е E p"' qEV L:q E dom(L)

6 2 max ^E P(L)z I^dom(L)I. ^qEV L:q E L

Указанные соотношения показывают, что величина, равная сумме правых частей (2.1), (2.3), (2.4), (2.6), (2.7), умноженная на два, подходит в качестве мажорирующего полинома для применения локальной леммы в формулировке 1. Нам остается лишь осуществить подходящий выбор параметров.

• 4.    Выбор параметров и итоговые оценки

Итак, в качестве мажорирующего многочлена ш(г) выступит сумма правых частей (2.1), (2.3), (2.4), (2.6), (2.7), умноженная на два:

ш(г) = 2²ⁿ⁺¹p^n/3 • А(Н ) • zⁿ+

I Е(Н ) |m- 1

+2 Е Em,'

m =1 u =0

m — 1 ⁿ

А(Н )(пА(Н ))^m-1-u(NnA(H ))^u x

x2 ^,m^' ■'■ :2 N )^u—1(N — m • (n — 1) — n)^—1

• (_3^      (i — p)2n/3 • _2m-n ....,..• + m-1

-

+2 £ £m4m( n )а(Н>А(Н))m-1 m>lnn u=0      x/

u(NnA(H))ux

x2-(m^(n-1)+1)(2/N)u-1(N - m • (n — 1) — n) 1 • ^3-^     • 22(m^(n 1)+1+u) + m /\

+2 Е E m( m I (A(H))m—1nmNu • (1 + 2p)mn • 21—(n—1)mN-™z2((n-r)m+u) + 36m62lnn+1 и=0/

1 n—s

+2 E E 2А(Н)ns(nN)2—s(1 + 2p)2n • 21+s—2nN—uz4n.(4.1)

Осуществим следующий выбор параметров:

1          1          1 5ln п п + 1 ’     1 — у п п

Напомним, что по условию теоремы А(Н) 6 с • 2”-1.

Теперв оценим каждое из составляющих (4.1) по отдельности. Нам необходимо показать, что w(1/(1 — у)) 6 у.

• 1)    Рассмотрим первое слагаемое:

2²”⁺¹р”^/3 • А(Н) • г” 6 2²”⁺¹ (5-^) / • с • 2”^-1 • е 6

6 се • 2 3 " ( nІ"/ ' 6 У у пу 5

при всех достаточно больших п > пд.

• 2)    Рассмотрим второе слагаемое:

|Е ( Н ) | т - 1           _

2 ^{Е Е} т4^т( ^т   )A(H)(пА(Н ))^т-1

т =1 п =0             '

-

^и (NпA(H))^их

_х2^-(m•⁽”^-1) + ¹⁾(2/N )“^-1(N —т • (п — 1) — u)^-1 • (^)     (1 — р)²”^/3 • - 2^т- ■'■■- 6

І Е(Н )| т -1         z        х

6 2 ^{Е Е} т4^т( ^т )(с • 2 ” ^-1)^mп^m-1N ^их т =1 п =0             '

х2^-(m•⁽”^-1) + ¹⁾(2/N)“^-1(N — т • (п — 1) — u)^-1 • ( 3^

т - 1

п-10/3 • е2т 6

1 Е(Н ) | т-1        ,

6 Е Е т4т^ — 1) Nх т =1 п =0             '

x 2^{m - 1}(N — т • (п — 1) — u)^-1 • (3)    п^-10/3 •

(разобьем сумму по т на две части: либо тп 6 N/2, либо тп

е2т 6

(N — т • (п — 1) — u) >  N/2^ во втором мы оценим это выражение единицей)

> N/*2. в первом случае

NJ ² ” т - 1      /     1 \                      / ^ \ т - 1

6 Е Ет4^т(^т — )c^mN2^й-1 (N/2)^-1 • (|j =  =

п-10/3 • е2т+

т- 1

+ Е Ет4т т>1Ч/2п и=0

т — 1\

u

cmN 2й-1

■( 2)

т - 1

п-10/3 •

е2т =

N/2”

^Е т4^т3^т-1с^т т =1

• (3 )т-1

п-10/3 •

е2т+

+ Е Nт4m3m-1 ст m>N/2n

• (3 Г1

п-10/3 •

е2т

При достаточно малой константе с <  1/500 первая сумма будет иметь порядок О(п^-10/3) < у/10. а. вторая сумма, будет иметь порядок O(N (18е²c)^N/2"п^-10/3). что также меньше, чем у/10 при всех достаточно бо.твших п > пе- т.к. N >  ”3.

• 3)    Третья сумма практически аналогична второй, за исключением отсутствия множителя (1 — p)^2n/3. Стало быть, она не превосходит

  N /2п

  
  

  ^Е m4^m3^m—1

  
  

  c^m

  
  

  m=ln n

  
  

  • (2 Г

  
  

  • e^2m +

  
  

  ^E Nm4^m 3^m-1c^m

  
  

  m>N/2n

  
  

  • (3 Г

  
  

  • e^2m

  
  

Заметим, что при достаточно малой константе c первая сумма не превосходит 2(18e2c)^lnn, что меньше, чем у/10 при всех п >  hq. Вторая же сумма, как и раньше, будет иметь порядок O(N (18e²c)^N/2n). что также меньше у/10 при всех достаточно больших п >  uq.

• 4)    Рассмотрим четвертое слагаемое:

  m

  Е Е-С)

  3 6 m 6 2lnn+1 u=0   ⁴ '

  
  

  (А(Н))^m—1n^mN^u • (1 + 2p)^mn

  
  

  2 І — (n — 1)m n — u ^ 2((n - 1)m+u) 6

  
  
  
  

  m

  Е E m(^m c^m-1i^3-nп^m -n^10m • e^{2 m} u 3 6 m 6 2lnn+1 u=0   ^{x 7}

  
  

  = E

  
  

  2^mmc^m-12^3-nn^11m • e^2m 6

  
  

  3 < m < 2lnn+1

  
  

  6 2 3 — n^2 lnn+11

  
  

  E

  
  

  2^m mc^m—1 • e^2m

  
  

  3 6 m 6 2 lnn+1

  
  

При достаточно малой константе c оставшаяся сумма будет меньше 1, а выражение перед суммой стремится к нулю экспоненциально по п, стало быть, оно будет меньше у/5 при всех достаточно больших п >  uq.

• 5)    Осталось рассмотреть пятую сумму:

1 n — S

2 ^{Е Е} 2А(Н)n^s(nN)^2—s(1 + 2p) 2 ⁿ • 2^1+s—2nN ^—uz⁴ⁿ 6

• 1    n — s

6 2 Е Е 2c2n—Vn20 • 22—2ne4 = O(2—nn23), что значительно меньше, чем у/5 при всех достаточно больших п > uq.

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