ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 58

2022

Вып. 1

УДК 621.391 : 519.174 : 519.179.1

А.С. Семенов¹, Д.А. Шабанов²

ОЦЕНКИ ПОРОГОВЫХ ВЕРОЯТНОСТЕЙ

ДЛЯ СВОЙСТВ РАСКРАСОК СЛУЧАЙНЫХ ГИПЕРГРАФОВ

Статья посвящена изучению пороговой вероятности для свойства наличия

раскраски в r цветов специального вида у случайного k-однородного гипергра-

фа в биномиальной модели H(n, k, p). Рассматривается параметрическое мно-

жество j-хроматических чисел случайного гиперграфа. Раскраска множества

вершин гиперграфа называется j-правильной, если в ней каждое ребро содер-

жит не более j вершин каждого цвета. Исследуется вопрос о нахождении точной

пороговой вероятности наличия j-правильной раскраски в r цветов у H(n, k, p).

С помощью метода второго момента получены весьма точные оценки этой ве-

личины при условии, что k и j велики по отношению к r.

Ключевые слова: случайный гиперграф, раскраски гиперграфов, j-хроматичес-

кое число, метод второго момента.

DOI: 10.31857/S0555292322010053

§ 1. Введение

В данной статье рассматривается одна из центральных задач в теории случайных

графов и гиперграфов о нахождении предельного распределения хроматических чи-

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

напомним их определения.

1.1. Определения. Пусть H = (V, E) - гиперграф с множеством вершин V и

множеством ребер E, а j ≥ 1 - некоторое натуральное число. Подмножество вершин

W ⊂ V называется j-независимым, если каждое ребро H имеет не более j общих

вершин с W, т.е. |W ∩ A| ≤ j для любого A ∈ E. Отметим, что для k-однородного

гиперграфа имеет смысл рассматривать только j ≤ k-1, иначе любое подмножество

вершин гиперграфа будет j-независимыми. Экстремальные и вероятностные задачи,

касающиеся j-независимых множеств в гиперграфах, изучались, например, в [1-4].

Раскраской вершин гиперграфа H = (V, E) в r цветов является отображение

τ: V → {1, . . ., r}. Множества Vi = τ-1(i), i = 1, . . ., r, принято называть цветовы-

ми классами раскраски τ. Если каждый цветовой класс τ является j-независимым

множеством в H, то τ называется j-правильной раскраской гиперграфа H. Тем са-

мым, каждое ребро в j-правильной раскраске имеет не более j вершин каждого из

цветов. Минимальное количество цветов r, необходимое для j-правильной раскрас-

ки вершин H, называется j-хроматическим числом гиперграфа H и обозначается

¹ Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследо-

ваний в рамках научного проекта № 18-31-00348.

² Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследо-

ваний в рамках научного проекта № 20-31-70039 и частичной поддержке гранта Президента РФ

№ МД-1562.2020.1.

через χ_j(H). В случае k-однородного гиперграфа существует специальная класси-

фикация j-хроматических чисел. Для j ≥ k/2 эти числа называются слабыми, а для

j < k/2 - сильными. Суть разделения понятна: в случае j ≥ k/2 неправильно рас-

крашенное ребро содержит лишь одно большое одноцветное подмножество вершин.

Наиболее распространен случай j = k - 1, который соответствует классическому

понятию хроматического числа гиперграфа χ(H).

В данной статье рассматривается проблема нахождения точной пороговой ве-

роятности наличия j-правильной раскраски в заданное число цветов у случайного

k-однородного гиперграфа в биномиальной модели H(n, k, p), n > k ≥ 2, p ∈ (0, 1).

Напомним, что случайный гиперграф H(n, k, p) образуется в виде схемы Бернул-

ли на ребрах полного k-однородного гиперграфа Knk) на n вершинах: каждое реб-

ро Knk) включается в H(n, k, p) в качестве ребра независимо и с вероятностью p.

Для k = 2 модель H(n, 2, p) очень хорошо известна как G(n, p), биномиальная мо-

дель случайного графа, еще называемая моделью Эрдеша-Реньи. Все эти модели

являются классическим и центральным объектом изучения в вероятностной ком-

бинаторике. Везде в статье мы предполагаем, что r ≥ 2, k ≥ 2 и 1 ≤ j ≤ k - 1

фиксированы, n стремится к бесконечности и p = p(n) ∈ (0, 1) - функция от n.

1.2. Известные результаты. Асимптотическое поведение хроматического числа

случайного графа G(n, p) изучается еще с 70-х годов прошлого века. Лучшие теку-

щие результаты описаны, например, в [5, 6]. Отметим лишь, что точное предельное

распределение можно найти только в разреженном случае, когда математическое

ожидание числа ребер является линейным по числу вершин n, т.е. p = p(n) = c/n

для некоторого фиксированного параметра c > 0. В этом случае известно, что хро-

матическое число имеет фиксированное предельное значение r = r(c) для почти всех

значений c, а для оставшихся небольших интервалов значений c существует двух-

точечная концентрация в двух последовательных натуральных числах. Основные

понятия и теоремы относительно сходимости по распределению в теории вероятно-

стей могут быть найдены читателем в главе 3 книги [7].

Гораздо труднее дело обстоит с j-хроматическим числом H(n, k, p). Асимптотиче-

ское поведение χ_j (H(n, k, p)) изучалось в работах [8-10], а также [11]. Перечисленные

результаты можно кратко описать следующим образом.

)

⁽n-j-1

1. Если для p = p(n) выполнено p

/ ln n → ∞, тогда с вероятностью,

k-j-1

стремящейся к 1 при n → ∞, j-хроматическое число случайного гиперграфа

сравнимо с j-хроматическим числом полного гиперграфа χ_j(Knk)) = ⌈n/j⌉, т.е.

P(χ_j (H(n, k, p)) = ⌈n/j⌉) → 1 при n → ∞.

Например, это соотношение будет выполнено при любом фиксированном p ∈ (0, 1)

и любом j < k -1. Отметим, что случай j = k -1 является особым. При фиксиро-

ванном p ∈ (0, 1) хроматическое число χk-1(H(n, k, p) будет иметь порядок o(n)

(см., например, [8]).

)

⁽n-1

2. Обозначим через d = p

математическое ожидание степени вершины в

k(-1

)

k-1

H (n, k, p), и пусть dj = j

d. Если для d = d(n) выполнено d → ∞ и

dn^-j → 0 при n → ∞ (т.е. pnk-1 → ∞ и pnk-1-j → 0), тогда (см. [11]) для

χ_j(H(n, k, p)) выполнен закон больших чисел:

(

)-1/j

d_j

χ_j(H(n, k, p))

-→ 1

при n → ∞.

(j + 1) ln d_j

3. Если d_j фиксировано, но больше некоторой абсолютной константы d₀, то имеет

место следующая концентрация для значения j-хроматического числа (см. [11]):

с вероятностью, стремящейся к 1 при n → ∞, выполнено

(

)1/j

(

))1/j

d_j

≤ χ_j(H(n,k,p)) ≤

(j + 1) ln d_j

ln0,1

d_j

Для разреженного случая, т.е. для фиксированного d = d(n), в классическом

варианте j = k -1 более точные оценки были получены в работах [6,12,13]. Обозна-

∕(n)

чим u_r,k = rk-1 ln r -¹

ln r для r, k ≥ 2, и пусть p = cn

, где c > 0 - некоторый

положительный параметр.

1. Если c > u_r,k, тогда (см. [12])

P(χ(H(n, k, p)) > r) → 1 при n → ∞;

(1)

r-1

2. Если c < u_r,k -

+ O(k²r1-k/3 lnr) и k ≥ 4, тогда (см. [6])

P(χ(H(n, k, p)) ≤ r) → 1 при n → ∞;

(2)

ln r

3. Если r > r₀(k) велико относительно k ≥ 3 и c < u_r,k-ln2-1,01

, тогда (см. [13])

P(χ(H(n, k, p)) ≤ r) → 1 при n → ∞.

(3)

Грубо говоря, значение u_r,k почти является пороговым значением параметра c для

свойства наличия раскраски в r цветов. На интервале (u_r,k, ur+1,k) хроматическое

число сконцентрировано в точке r + 1 почти везде, кроме небольшого интервала

фиксированной величины. В зависимости от отношения r и k длина этого интервала

r-1

равна либо

+ o(1), либо ln 2 + o(1).

Особый интерес представляет поиск пороговой вероятности для свойств раскрас-

ки в два цвета. Поиску пороговой вероятности для свойства “хроматическое число

не превосходит двух” у случайного гиперграфа H(n, k, p) посвящены работы [14-16].

Наилучший результат был получен в [17], где авторы показали, что существует та-

∕(n)

кая функция ε_k = 2-k(1+ok(1)), что при p = cn

ln 2

c < 2k-1 ln2 -

-ε_k

выполнено P(χ(H(n, k, p)) ≤ 2) → 1 с ростом n, а для

ln 2

c > 2k-1 ln2 -

+ε_k

выполнено P(χ(H(n, k, p)) > 2) → 1 при n → ∞. Тем самым, пороговое значение

параметра c удалось локализовать с точностью до интервала, длина которого стре-

мится к нулю с ростом k. Подобный эффект был также обнаружен в статье [18], где

√

для свойства “j-хроматическое число H(n, k, p) не превосходит двух ” при k-j <

были получены такие верхняя и нижняя оценки порогового значения параметра c,

что разность между ними стремится к нулю с ростом k.

Однако для раскрасок в большее число цветов похожих результатов в общем

случае пока добиться не удалось. Даже для классического хроматического числа

остается зазор порядка O(1) для свойства наличия правильной раскраски в r ≥ 3

цветов (см. вышеперечисленные результаты 1-3 из работ [6, 12, 13]).

1.3. Новый результат. Основной результат данный статьи дополняет ранее из-

вестные результаты и дает очень точные оценки пороговой вероятности для свой-

ства наличия j-правильной раскраски в r цветов у случайного гиперграфа H(n, k, p)

при j < k - 1, j ∼ k и r ≪ k. Точная формулировка выглядит следующим образом.

Теорема 1. Пусть H(n,k,p) - случайный k-однородный гиперграф на n вер-

∕(n)

шинах, где p = cn

и c = c(k,j,r) > 0 не зависит от n. Для любого r > 2

существуют такие положительные числа C_ℓ = C_ℓ(r), C_u = C_u(r) и k₀ = k₀(r),

что при k > k₀ и 1 < k - j < k1/4 выполнено следующее:

Если

(

)

rk-1 lnr

ln r

+C_u

r^-j,

(4)

∑ (k)

j+1

(r - 1)^s

s=0

то с вероятностью, стремящейся к 1 при n → ∞, χ_j (H (n, k, p)) > r;

Если

rk-1 lnr

ln r

-C_ℓk(j-k+1)/2,

(5)

∑ (k)

(r - 1)^s

s=0

то с вероятностью, стремящейся к 1 при n → ∞, χ_j (H (n, k, p)) ≤ r.

Прокомментируем результаты теоремы.

При фиксированном r и k - j < k1/4 (а значит, j ∼ k) разность между получен-

ными оценками порогового значения c стремится к нулю с ростом k. Это замеча-

тельный эффект, который, как видно из полученных выражений, не получается в

классическом случае j = k-1. Данный феномен мы пока можем объяснить лишь

техническими особенностями применения метода второго момента, который мы

используем для доказательства теоремы 1, хотя вполне может оказаться, что име-

ет место некоторая особенность множества j-правильных раскрасок случайного

гиперграфа при j < k - 1.

Ограничение k-j < k1/4, по-видимому, не является оптимальным даже в рамках

применяемого метода. Например, как будет видно из доказательства в § 2, оцен-

ка (4) верна и при k - j = o(k/ ln k). Однако учитывая техническую сложность

вычислений, нам было важно показать, что теорема верна в достаточно широком

диапазоне значений параметров.

С точки зрения изучения собственно распределения j-хроматического числа

H (n, k, p) представляет интерес обратная ситуация, когда r ≫ k. Здесь были

исследованы некоторые частные случаи. Случай j = 1, k = 3 можно найти в ра-

боте [19], а случай j = k - 2 - в работе [20]. В обеих работах полученные оценки

пороговой вероятности имеют зазор, стремящийся к положительной константе

при r → ∞.

§ 2. Доказательство верхней оценки

Для доказательства верхней оценки обратимся к другой модели случайного ги-

перграфа H^′(n, k, m), где m = ⌈cn⌉ и выполнено неравенство (4). В этой модели

независимо, равномерно и с возвращением набираются m ребер из всевозможных

k-подмножеств вершин. Обозначим через Z_n число различных ребер в H^′(n, k, m).

Нужно отметить, что Z_n может быть меньше m, если некоторые случайные ребра

совпадут.

∕(n)

Пусть p^′ = c^′n

, причем c^′ > c. Тогда покажем, что

(

)

(

)

P χ_j(H^′(n,k,m)) > r

≤ P χ_j(H(n,k,p^′)) > r

+ o_n(1).

Действительно, возьмем случайную перестановку σ ребер полного гиперграфа Knk).

Да(( р)сс )отрим две независимые с σ случайные величины: ξ1 с распределением

Bin

,p^′ и ξ₂, имеющую то же распределение, что и Z_n. Тогда с точки зрения

распределения

• гиперграф H₁, образованный первыми ξ₁ ребрами согласно σ, есть H (n, k, p^′);

• гиперграф H₂, образованный первыми ξ₂ ребрами согласно σ, есть H^′ (n, k, m).

Случайные величины ξ₁ и ξ₂ сильно сконцентрированы вокруг своих средних: E ξ₁ =

= c^′n, E ξ₂ ∼ cn, Dξ₁ = O(n), Dξ₂ = O(n), и значит, из неравенства Чебышева

следует, что P(ξ₁ > ξ₂) → 1 при n → ∞. Следовательно, с вероятностью, стремя-

щейся к 1, гиперграф H₁ содержит H₂, и нам остается показать, что

(

)

P χ_j(H^′(n,k,m)) > r

→ 1, n → ∞.

Пусть τ - произвольная раскраска вершин гиперграфа H^′(n, k, m) в r цветов.

∑

Обозначим через v₁, . . ., v_r мощности ее цветовых классов ( v_i = n). Тогда веро-

i=1

ятность того, что τ является j-правильной раскраской H^′(n, k, m), равна

(

∑

∑(_v

⁾⁽n - v_i)∕(n))m

(6)

k-s

i=1

s=0

Поясним выражение (6). В силу условия теоремы k - j < k1/4 < k/2. Значит, если

ребро неправильно покрашено в раскраске τ, то в нем существует единственный блок

из хотя бы j + 1 > k/2 одинаково покрашенных вершин. Остальные вершины могут

быть раскрашены произвольным образом. Следовательно, в раскраске τ есть в точ-

∑

∑ (vi )(n-vi)

ности

неправильно раскрашенных k-подмножеств, и ни од-

k-s

i=1

s=0

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

Для оценивания выражения (6) понадобится следующая

Лемма 1. Пусть k,j,r,v₁,...,v_r ∈ N таковы, что r > 2 и 2 < k-j < k1/4. Су-

∑

ществует k₀ = k₀(r), такое что при k ≥ k₀ и любых v₁, . . . , v_r с условием

v_i = n

выполнено

i=1

(

∑

v_i

⁽ n/r ⁾⁽n - n/r⁾

≥r

+ o(n^k), n → ∞.

(7)

k-s

i=1

s=0

Доказательство. Правую часть неравенства можно оценить следующим об-

разом:

∑

⁽ n/r⁾⁽n - n/r⁾

⁽k⁾⁽n⁾k-s⁽n(r - 1))s

≤

k-s

s=0

Оценим левую часть

(

∑

v_i

⁾⁽n - v_i)

∑ (k⁾

v^k-si(n - v_i)^s + o(n^k).

k-s

i=1

s=0

i=1

s=0

∑ (k)

Рассмотрим функцию f(x) =

x^k-s(n - x)^s. Для нее выполнено

s=0

∑

⁽k⁾

f^′(x) = kxk-1 +

xk-s-1(n - x)s-1(n(k - s) - kx),

s=1

∑

⁽k⁾

f^′′(x) = k(k - 1)xk-3((1 - k)x + n(k - 2)) +

xk-s-2(n - x)s-2 ×

s=2

[

]

k(k - 1)x² - 2n(k - 1)(k - s)x + n²(k - s)(k - s - 1)

Наименьший корень квадратного трехчлена в скобках можно найти явно и оценить

следующим образом:

√

(k - 1)(k - s) -

s(k - 1)(k - s)

x_min = n

≥

k(k - 1)

(при s ≤ k/2 минимум данного выражения достигается при s = k/2)

√

k-1-

k-1

≥n

√

≥

2(k - 1)

k-1

начиная с k = 17. Следовательно, на отрезке [0, 3n/8] функция f(x) возрастает и

выпукла вниз. Значит, если все v_i ∈ [0, 3n/8], то из неравенства Йенсена (E f(ξ) ≥

≥ f(Eξ) для выпуклой вниз функции f(x) и случайной величины ξ) следует искомое

соотношение

∑

⁽k⁾

k-s

⁽k⁾⁽ n⁾k-s⁽n(r - 1))s

v_i

(n - v_i)^s ≥

i=1

s=0

Пусть теперь, например, v₁ > 3n/8, тогда левая часть в выражении (7) заведомо

больше, чем

)_k

∑(_v

⁾⁽n - v₁)

(v₁ - k)^k

1 (n⁾k⁽3r

≥

k-s

k! r

s=0

в то время как

∑

⁽k⁾⁽ n⁾k-s⁽n(r - 1))s

1 (n

⁽k⁾

(r - 1)^s ≤

k! r

s=0

)_k

∑

)_k

1 (n

≤

rkk-j-1rk-j-1

≤

kk-j-1r^k-je.

k! r

s=0

Следовательно, при r ≥ 3 и k - j < k1/4, начиная с некоторого k₀(r), неравенство (7)

также будет выполнено. ▴

Замечание. Отметим, что доказательство леммы 1 работает и при более слабых

ограничениях на разность k - j. Например, достаточно потребовать, чтобы k - j =

= o(k/ ln k).

Из леммы следует, что выражение в скобках в (6) максимально при почти равных

значениях v₁, . . . , v_r, а значит, математическое ожидание числа искомых раскрасок

H^′(n, k, m) не превосходит

⎛

(

⎞

∑

n/r

⁾⁽n - n/r⁾

⎜

k-s

⎟

rⁿ

⎜1-s=0

+ o_n(1)⎟

≤

⎝

⁽n⁾

⎠

(

)⌈cn⌉

∑

⁽k⁾

≤rⁿ

1-r1-k

(r - 1)^s + o_n(1)

s=0

( [

(

)

])

∑

⁽k⁾

= exp n lnr + c ln

1-r1-k

(r - 1)^s

+ o_n(1)

s=0

Заметим, что последнее выражение стремится к нулю с ростом n (а значит, то же

- ln r

самое происходит с вероятностью того, что χ_j(H^′(n, k, m)) ≤ r) при c >

ln(1 - q)

∑

где q = r1-k

⁽k)(r-1)s. При этом верно, что

s=0

− ln r

ln r

≤

(1 - q/2 + q²/3) =

ln(1 - q)

q + q²/2 + q³/3

rk-1 ln r

ln r

q ln r

∑ (k)

(r - 1)^s

s=0

((

)

Учитывая, что q = O

r-j , верхняя оценка (4) доказана.

j+1

§ 3. Доказательство нижней оценки

Доказательство нижней оценки основывается на методе второго момента. Дока-

зательство будет проведено в несколько шагов и следует идеям из работы [6].

3.1. Точная пороговая вероятность. Необходимым условием для нашего приме-

нения метода второго момента является наличие точной пороговой вероятности для

свойства χ_j(H) ≤ r. Напомним, что наличие точной пороговой вероятности означа-

ет, что для любых фиксированных r, j, k существует некоторая функция p = p(n),

такая что для любого ε > 0

(

)

^{1, если p < (1 - ε)p,

χ_j(H(n, k, p)) ≤ r

→

0, если p > (1 + ε)p.

Для обоснования ее существования воспользуемся следующим результатом из [21].

Теорема 2 [21, теорема 5]. Пусть k ≥ 3. Пусть F = (V^′,E^′) - фиксирован-

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

упорядоченные наборы из k вершин (т.е. вершины в ребрах могут повторяться)

и который не содержит петель (ребер, в котором все вершины совпадают). То-

гда свойство наличие гомоморфизма из случайного гиперграфа H(n, k, p) в F имеет

точную пороговую вероятность.

В нашем случае гиперграф H(n, k, p) обладает свойством χ_j (H(n, k, p)) ≤ r то-

гда и только тогда, когда существует гомоморфизм из H(n, k, p) в гиперграф F =

= (V ^′, E^′), где

{

}

V ′ = {1,...,r}, E^′ =

(a₁, . . . , a_k) : maxcount(a₁, . . . , a_k) < j + 1

а maxcount(a₁, . . . , a_k) обозначает максимальное количество одинаковых значений

среди a₁, . . . , a_k.

В силу существования точной пороговой вероятности достаточно показать, что

вероятность наличия рассматриваемого свойства отделена от нуля. Действительно,

если для некоторого c > 0 мы покажем, что

( (

(

)

^∕(n⁾⁾⁾

lim inf

P χ_j H n,k,cn

≤r

> 0,

(8)

n→∞

(

( (

)

∕(n)))

то для любого c^′ < c вероятность P χ_j H n, k, c^′n

≤ r уже будет стремить-

)

∕(n

ся к 1, так как величина c^′n

будет заведомо меньше пороговой вероятности.

3.2. Снова равномерная модель. При доказательстве нижних оценок мы также

будем использовать другую модель случайного гиперграфа. Рассмотрим случай-

ный гиперграф H^′′(n, k, m), где m = ⌈cn⌉, состоящий из m независимых случай-

ных k-подмножеств множества вершин, причем и в каждом таком k-подмножестве

все k вершин выбираются случайно, независимо и равновероятно. В таком гипергра-

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

повторяющиеся вершины. Легко убедиться с помощью неравенства Чебышева, что

число полных ребер (из k различных вершин) H^′′(n, k, m) с вероятностью, стремя-

щейся к 1, будет лежать в O(n1/2 lnn)-окрестности числа cn. Действительно, эта

случайная величина имеет биномиальное распределение Bin(m, 1 + O(1/n)), а пото-

му сильно сконцентрирована вокруг своего среднего значения, равного cn + O(1).

∕(n)

Значит, при c^′ < c, вновь используя обозначение p^′ = c^′n

(

)

(

)

P χ_j(H(n,k,p^′)) ≤ r

≥ P χ_j(H^′′(n,k,m)) ≤ r

+ o_n(1).

Следовательно, вместо (8) достаточно показать, что выполнено

(

)

lim inf

χ_j(H^′′(n, k, m)) ≤ r

> 0.

(9)

n→∞

Отметим, что при поиске j-правильной раскраски гиперграфа H^′′(n, k, m) для его

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

j + 1 вершин.

3.3. Подсчет числа раскрасок. Заметим, что с вероятностью, стремящейся к 1

при n → ∞, в рассматриваемом гиперграфе будет много изолированных вершин.

С помощью этого факта несложно проверить, что достаточно установить (9) толь-

ко для подпоследовательности n, кратных r (см. [12, лемма 1.4]). С учетом этого

для доказательства неравенства (9) рассмотрим так называемые сбалансированные

раскраски. Раскраска называется сбалансированной, если все ее цветовые классы

имеют одинаковую мощность. Пусть X_n - количество j-правильных сбалансирован-

ных раскрасок случайного гиперграфа H^′′(n, k, m) в r цветов, тогда

(

)

χ_j(H^′′(n, k, m)) ≤ r

≥ P(X_n > 0),

а в силу неравенства Пэли-Зигмунда

(E X_n)

P(X_n > 0) ≥

EX²

Таким образом, остается показать, что

EX2n = O_k,j,r((EX_n)²).

(10)

3.4. Подсчет моментов. Найдем первый момент числа j-правильных сбалансиро-

ванных раскрасок

(

)

EX_n =

(1 - q)^⌈cn⌉ = Θ_k,j,r

n-(r-1)/2 exp(n[ln r + c ln(1 - q)])

(11)

((n/r)!)^r

где величина q означает вероятность того, что при фиксированной сбалансирован-

ной раскраске хотя бы j + 1 вершин случайного ребра будут покрашены в один и

тот же цвет. Эту вероятность нетрудно вычислить аналитически. По условию тео-

ремы k - j < k1/4 < k/2, и значит, подобный одноцветный набор вершин может

быть только один. Так как раскраска сбалансированная, то вероятность того, что

случайно выбранная вершина окажется окрашенной в какой-либо конкретный цвет,

равна 1/r. Тогда вероятность того, что при случайном независимом равновероят-

ном выборе k вершин ребра ровно s вершин окажутся именно этого цвета, равна

⁽k⁾

r^-k

(r - 1)^k-s. Учитывая все цвета и суммируя по всем s, не меньшим чем j + 1,

получим

∑

⁽k⁾

q=r1-k

(r - 1)^k-s = r1-k

(r - 1)^s.

s=j+1

s=0

Мы уже вводили это обозначение в конце § 2. Множитель

соответствует

((n/r)!)^r

числу всех сбалансированных раскрасок в r цветов. Величина 1 - q означает веро-

ятность того, что в сбалансированной раскраске никакие j + 1 вершин случайного

ребра не будут покрашены в один цвет. Так как ребра выбираются независимо, то

данную величину необходимо возвести в степень, равную количеству ребер, т.е. ⌈cn⌉.

Второй момент вычисляется несколько сложнее. Для краткости будем называть

ребро плохим в некоторой раскраске, если оно имеет хотя бы j + 1 вершин одного и

того же цвета. Пусть τ₁, τ₂ - две сбалансированные раскраски, а e - случайное ребро

гиперграфа H^′′(n, k, m). Найдем вероятность того, что в обеих раскрасках никакой

набор e из j + 1 вершин не покрашен в один и тот же цвет. Для этого рассмотрим

класс A матриц размера r × r, у которых все элементы являются целыми неот-

рицательными числами, а сумма в каждой строке и в каждом столбце равна n/r.

Матрицы такого вида отлично представляют собой пары r-цветных сбалансирован-

ных раскрасок вершин гиперграфа H^′′(n, k, m). Если A ∈ A, A = (a_iu, i, u = 1, . . . , r),

то будем считать что a_iu - это число вершин, имеющих цвет i в раскраске τ₁ и цвет u

в раскраске τ₂. Для раскрасок τ₁, τ₂ вероятность того, что e будет раскрашено плохо

хотя бы в одной из них, зависит лишь от матрицы A. Обозначим эту вероятность

через Q(A). Далее, матрица A ∈ A представляет

∏

a_iu!

i,u=1

пар сбалансированных раскрасок. Вероятность того, что и τ₁, и τ₂ являются j-пра-

вильными раскрасками H^′′(n, k, m), равна (1-Q(A))^⌈cn⌉. Стало быть, второй момент

случайной величины X_n будет равен

(

)-1

∑

∏

EX2n = n!

a_iu!

(1 - Q(A))^⌈cn⌉.

(12)

A∈A i,u=1

Осталось найти Q(A). Напомним, что вероятность того, что случайное ребро являет-

ся плохим в раскраске τ_i, i = 1, 2, равна q. Теперь рассмотрим событие, при котором

ребро будет плохим в обеих раскрасках, а именно событие, состоящее в том, что

ребро содержит хотя бы j + 1 вершин цвета i в первой раскраске и хотя бы j + 1

вершин цвета u во второй раскраске. Пусть s - число вершин ребра, покрашенных

в цвет i в первой раскраске, t - число вершин ребра, покрашенных в первой рас-

краске в цвет i, а во второй - в любой цвет, кроме u, и наконец, h - число вершин

ребра, покрашенных во второй раскраске в цвет u, а в первой - в любой цвет, кроме

цвета i. Тогда в ребре во второй раскраске будет ровно h + s - t вершин цвета u.

Интересующее нас событие имеет место быть, если и только если

j+1≤s≤k,

0 ≤ h ≤ k - s, h + s - t ≥ j + 1.

(13)

Последнее вытекает из того, что во второй раскраске должно быть не менее j + 1

вершин цвета u. Далее, в силу свойств матрицы A

• каждая вершина цвета i в первой раскраске и цвета u во второй может быть

выбрана a_iu способами, всего таких вершин s - t;

• каждая вершина цвета i в первой раскраске и не цвета u во второй может быть

выбрана n/r - a_iu способами, всего таких вершин t;

• каждая вершина не цвета i в первой раскраске и цвета u во второй может быть

выбрана n/r - a_iu способами, всего таких вершин h;

• наконец, вершина не цвета i в первой раскраске и не цвета u во второй может

n(r - 2)

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

+ a_iu способами,

всего таких вершин k - h - s.

Тогда вероятность искомого события будет равна

∑

∑ (k-s)(s)

s=j+1

h=0

t=0

(_n

)h+t

(n(r-2)

)k-h-s

-a

+a_iu

⁽aiu )s-t

× r

Осталось просуммировать по всем i и u. Таким образом, вероятность Q(A) того, что

ребро будет плохим хотя бы в одной из раскрасок, будет равна

∑

∑ (k-s)(s)

Q(A) = 2q -

i,u=1 s=j+1

h=0

t=0

(_n

)h+t

(n(r-2)

)k-h-s

-a

+a_iu

⁽aiu )s-t

× r

(14)

Теперь, применяя оценки Стирлинга вида x! = Θ((x/e)^x

√x + 1) к выражению

в (12), получим

(

)-1

∑

∏

√

EX2n =Θ_k,j,r

n1/2

a_iu + 1

A∈A i,u=1

( [

]))

∑

)

⁽a_iu)

⁽a

× exp n -

+ cln(1 - Q(A))

(15)

i,u=1

Введем следующие обозначения: для A ∈ A

∑

a_iu

ra_iu

H(A) = -

i,u=1

E (A) = ln(1 - Q(A)).

Для c > 0 обозначим G_c(A) = H(A) + cE(A). Дальнейшая наша цель будет состоять

в обосновании того факта, что в условиях теоремы функция G_c(A) достигает своего

максимума при A = J_r, где J_r - матрица, все элементы которой равны n/r². Для

этого сначала вычислим G_c(J_r).

Утверждение 1. Для любых r,k,j ∈ N, таких что k/2 < j < k, выполнено

G_c(J_r) = lnr + c ln(1 - q)².

Кроме того, имеет место тождество

)h+t (

)_s-t (

)_k-h-s

∑

∑ (k-s)(s)(1

(r - 1)²

q²

r²

s=j+1

h=0

t=0

Доказательство утверждения 1 сугубо техническое, мы приведем его в § 6, а пока

продолжим рассуждения.

Из (11), (12) и утверждения 1 получаем следующую оценку EX2n:

(

)-1

∑

∏

√

EX2n = Θ_k,j,r (EX_n

)²nr-1/2

a_iu + 1

A∈A i,u=1

( [

]))

∑

a_iu

× exp n -

+ cln(1 - Q(A)) - lnr² - cln(1 - q)²

i,u=1

( [

]))

∑

a_iu

ra_iu

= exp n -

+ cln(1 - Q(A)) - G_c(J_r)

i,u=1

(

)-1

)

∑

∏r

(

√

[

])

= Θ_k,j,r (EX_n

)²nr-1/2

a_iu + 1

exp n

G_c(A) - G_c(J_r)

A∈A i,u=1

Для завершения доказательства нам понадобится следующая

Лемма 2. Если выполнено условие (5), то существует функция b = b(k,r) > 0,

такая что для любой матрицы A = (a_iu, i, u = 1, . . ., r) из A выполнено

)₂

∑

⁽a_iu

G_c(J_r) - G_c(A) ≥ b

(16)

r²

i,u=1

Иными словами, на матрицах класса A максимальное значение G_c достигается

именно на матрице J_r. Доказательство леммы будет приведено в следующем пара-

графе, а здесь заметим, что для любого a_iu = 0, . . ., n/r выполнено

(√

)-1

a_iu + 1

e^-nb(^anu

r²

)² = O_k,j,r(n-1/2).

Применяя эту оценку ко всем парам i, u, таким что max(i, u) = r, а также лемму 2,

можно оценить второй момент случайной величины X_n следующим образом:

(

)

∑

-1 (√

)-1

)²

EX2n = O_k,j,r (EX_n

)²

a_iu + 1

e^-nb(^anu

r²

A∈A i,u=1

Учитывая, что числа (a_iu, i, u = 1, . . . , r - 1) однозначно определяют матрицу A,

полученная сумма по матрицам не превосходит полной суммы по всем значениям a_iu,

i, u = 1, . . ., r - 1, от 0 до n/r. Стало быть,

⎛

(

)(r-1)² ⎞

∑

-¹

)²

EX2n = O_k,j,r ⎝(EX_n

)²

√ e^-nb(

r²

⎠.

a+1

a=0

Следовательно,

⎛

(∫∞

)(r-1)² ⎞

(

)

)²

⎠=Ok,j,r

EX2n ≤ O_k,j,r ⎝(EX_n

)²

r²

(E X_n)²

√x + 1e-nb(ⁿ

∫

в силу того, что

√x + 1e-nb(x/n-1/r2)² dx=Ok,r(1).Значит,неравенство(10)вы-

полнено и нижняя оценка доказана. Осталось лишь доказать лемму 2, чему и будет

посвящен следующий параграф.

§ 4. Доказательство леммы 2

В этом параграфе мы покажем справедливость неравенства (16). Из формули-

aiu

ровки видно, что нам будет удобно также пользоваться “заменой” ε_iu =

r²

i, u = 1, . . ., r. В данных обозначениях (16) можно переформулировать следующим

образом:

∑

a_iu

ra_iu

G_c(J_r) - G_c(A) = lnr + c(1 - q)² +

- cln(1 - Q(A)) =

i,u=1

∑

a_iu

r²a_iu

⁽1 - Q(A)⁾

- cln

(1 - q)²

i,u=1

)

(

)

∑

⁽ 1

-Q(A) + 2q - q²

+ ε_iu ln(1 + r²ε_iu) - cln 1+

(17)

r²

(1 - q)²

i,u=1

В силу (14) величина Q(A) - 2q + q² будет равна

∑

∑ (k-s)(s)

- Q(A) + 2q - q² =

i,u=1 s=j+1

h=0

t=0

)h+t (

)_s-t (

)_k-h-s

⁽1

(r - 1)

-ε_iu

+ε_iu

-q².

(18)

r²

Введем матрицу Υ = (ε_iu, i, u = 1, . . . , r) и отметим ее свойства: все элементы

принадлежат отрезку [-1/r², 1/r - 1/r²], а также суммы элементов по всем строкам

и столбцам равны нулю, т.е. формально - для любых i, u = 1, . . . , r

[

]

∑

ε_iu ∈

ε_i′_u = 0,

ε_iu′ = 0.

(19)

r²

i′=1

u^′=1

Неравенство (16) можно переформулировать так: существует такая b = b(k, r), что

для любой матрицы Υ = (ε_iu, i, u = 1, . . . , r) со свойствами (19) выполнено

∑

G_c(J_r) - G_c(A) ≥ b

ε2iu.

i,u=1

Рассмотрим следующие функции строк для каждого i = 1, . . . , r:

)

∑( 1

(

)

H_i(Υ) =

+ ε_iu ln

1+r²ε_iu

r²

u=1

[

∑

∑ (k-s)(s)

E_i(Υ) =

(1 - q)²

u=1 s=j+1

h=0

t=0

]

)h+t (

)_s-t (

)_k-h-s

⁽1

(r - 1)

-ε_iu

+ε_iu

- q²/r .

r²

Из (17), (18) получаем, что

( ∑r

) ∑r

∑

(

)

G_c(J_r) - G_c(A) =

H_i(Υ) - c ln

1 + E_i(Υ)

≥

H_i(Υ) - cE_i(Υ)

(20)

i=1

Далее будем исследовать разность H_i(Υ)-cE_i(Υ). Будем классифицировать строки

матрицы Υ на центральные, хорошие и плохие в зависимости от максимального

значения элементов следующим образом:

• строка с номером i - центральная, если

0 ≤ max

ε_iu <

;

u=1,...,r

r²

rk2/3

• строка с номером i - хорошая, если

]

^[1

max

ε_iu ∈

-r-2k/3 ;

u=1,...,r

r²

rk2/3

r²

• строка с номером i - плохая, если

]

⁽1

max

ε_iu ∈

-r-2k/3,

u=1,...,r

r²

Начнем с анализа центральных строк.

4.1. Центральные строки.

Утверждение 2. Для центральной строки с номером i выполнено

∑

H_i(Υ) - cE_i(Υ) ≥

ε2iu + a(r)

ε2iu,

(21)

u: εiu<0

u: εiu≥0

где a(r) > 0 - некоторая положительная функция от r.

Доказательство. Вначале оценим H_i(Υ). В сумме H_i(Υ) оценим слагаемые

(1/r² + ε_iu) ln(1 + r²ε_iu) по-разному в зависимости от ε_iu.

Случай 1. Если ε_iu < 0, то используем оценки функции ϕ(x) = (1 + x) ln(1 + x)

при x > -1, про которую известно, что

ϕ(x) > x +

для x < 0.

Тогда для x = r²ε_iu

(1/r² + ε_iu) ln(1 + r²ε_iu) ≥ ε_iu +

ε2iu.

(22)

Отметим, что неравенство (22) верно и при ε_iu = -1/r².

Случай 2. Если ε_iu > 0, но ε_iu ≤ 1/(r ln r) - 1/r², то снова используем оценки

функции ϕ(x) = (1 + x)ln(1 + x), про которую известно, что

ϕ(x) > x +

для x > 0.

2(1 + x/3)

Тогда при x = r²ε_iu

r²ε2iu

(1/r² + ε_iu) ln(1 + r²ε_iu) ≥ ε_iu +

≥

2(1 + r²ε_iu/3)

(оценим знаменатель 1 + r²ε_iu/3 < 1 + r/(3 ln r) - 1/3 < 2r/(3 ln r))

3r lnr

≥ε_iu +

ε2iu.

Случай 3. Наконец, если же ε_iu > 1/(r ln r) - 1/r², то оценим слагаемое следую-

щим образом:

)

( r

(1/r² + ε_iu) ln(1 + r²ε_iu) ≥ (1/r² + ε_iu) ln

≥

ln r

≥ ε_iu + ε_iu(lnr - lnlnr - 1) ≥

(

)-1

(воспользуемся тем, что 1 ≥ rε_iu

)

k2/3

(

)-1

≥ε_iu +rε2iu

(ln r - ln ln r - 1).

k2/3

Тем самым, в силу (19)

∑

r²

H_i(Υ) =

(1/r² + ε_iu) ln(1 + r²ε_iu) ≥

ε_iu +

ε2iu +

u=1

u: εiu<0

(

)-1

)

∑

3r lnr

+ min

(ln r - ln ln r - 1)

ε2iu =

k2/3

u: εiu>0

(

)-1

)

∑

3r lnr

ε2iu + min

(ln r - ln ln r - 1)

ε2iu.

k2/3

u: εiu<0

u: εiu>0

Далее оценим cE_i(Υ) сверху. Данная величина является полиномом относитель-

но ε_iu, причем в силу утверждения 1 свободный член в этом многочлене равен нулю.

Заметим также, что данный полином симметричен относительно ε_iu по u при фик-

сированном i в силу инвариантности задачи при переобозначении цветовых классов.

∑

Из свойств (19) матрицы Υ следует, что

ε_iu = 0, поэтому остается рассматривать

u=1

лишь коэффициенты при степенях ε_iu от второй и выше. Тогда E_i(Υ) можно оценить

следующим образом:

∑∑(k)

E_i(Υ) ≤

r2v|ε_iu|^v ×

(1 - q)²

u=1 v=2

[

)h+t (

)_s-t (

)_k-h-s]

∑

∑ (k-s)(s)(1

(r - 1)²

r²

s=j+1

h=0

t=0

)

⁽k

Прокомментируем неравенство. Коэффициент

получен исходя из того, что

)

(

)

⁽1

⁽(r - 1)²

из всех множителей вида

-εiu ,

+ε_iu и

+ε_iu в выражении

r²

для E_i(Υ) ровно в v случаях из k нужно взять ε_iu или -ε_iu. При этом мы получим

коэффициент вида

)h+t-α (

)_s-t-β (

)_k-h-s-γ

⁽1

(r - 1)²

r²

где α + β + γ = v. Ясно, что каждый подобный коэффициент не превосходит

)h+t (

)_s-t (

)_k-h-s

⁽1

(r - 1)

r2v

r²

Так как мы оцениваем сверху, то не берем в расчет знак ε_iu и рассматриваем только

абсолютное значение |ε_iu|. Далее, используя утверждение 1, получаем оценку

∑∑(k)

E_i(Υ) ≤

r2v-2q²|ε_iu|^v.

(1 - q)²

u=1 v=2

Если ε_iu < 0, то его модуль в силу (19) не превосходит 1/r², а в противном случае

ε_iu <

. Следовательно,

r²

rk2/3

[

∑

⁽k⁾

cE_i(Υ) ≤

ε²

r²q²+

(1 - q)²

u: εiu<0

v=2

]

)v-2

∑

⁽k⁾

⁽1

ε²

r2v-2

q²

≤

r²

rk2/3

u: εiu>0

v=2

[

∑

⁽k⁾

≤

ε²

r² +

(1 - q)²

u: εiu<0

v=2

]

)-2 (

)_k

∑

⁽1

ε2iur2k-2

≤

r²

rk2/3

u: εiu>0

(пользуясь тем, что c < ln r/q по условию (5))

[

]

(

)-2 (

)_k

q ln r

∑

≤

ε2iu2kr2 + r

ε²

≤

(1 - q)²

k2/3

u: εiu<0

u: εiu>0

(

(так как начиная с некоторого k выполнено

)^k ≤ e-k1/3 )

k2/3

(

)-2

∑

qr^k lnr 1-

e-k1/3

∑

qr²2^k lnr

k2/3

≤

ε2iu +

ε2iu.

(1 - q)²

u: εiu<0

u: εiu>0

∑

Остается оценить коэффициенты при

ε2iu и

ε2iu с помощью следую-

u: εiu<0

u: εiu>0

щего технического утверждения, доказательство которого вынесено в § 6.

Утверждение 3. Для любого r > 3 существует такое k₀ = k₀(r), что для

всех k, j ∈ N, таких что k - j < k1/4 и k > k₀, выполнены следующие неравенства:

(

)-2

1/3

qr^k lnr 1-

e^-k

qr²2^k lnr

r²

k2/3

≤

< e-10r lnr.

(1 - q)²

∑

Из вышеприведенного утверждения следует, что коэффициент при

ε2iu не

u: εiu>0

превосходит e-10r ln r, что сильно меньше3rlnr. Кроме того, выполнено

e-10r lnr <

r(ln r - ln ln r - 1).

В итоге из оценок H_i(Υ) и cE_i(Υ) следует, что при достаточно большом k

∑

H_i(Υ) - cE_i(Υ) ≥

ε2iu +

u: εiu<0

(

)-1

)

∑

3r lnr

+ min

(ln r - ln ln r - 1)

ε2iu.

k2/3

u: εiu>0

4.2. Хорошие строки. Строку с номером i мы называем хорошей, если нашелся

такой u₀, что

]

^[1

εiu0 = max

ε_iu ∈

-r-2k/3

u=1,...,r

r²

rk2/3

r²

Для простоты будем считать, что u₀ = 1. Введем параметр δ_i =

- εi1. Тогда

r²

δ_i ∈ [r-2k/3,

]. Далее, обозначим δ_iu =

+ ε_iu, u > 1. Отметим, что δ_iu ≥ 0 и

rk2/3

r²

^∑ δ_iu =δ_i в

силу (19).

u=2

Рассмотрим H_i(Υ) и E_i(Υ) как функции от δ_i, δ_iu. Нам достаточно показать, что

H_i(Υ) и cE_i(Υ) отличаются на некоторую величину a = a(k, r) > 0. Имеем

∑

H_i(A) = (1/r - δ_i)ln(r - r²δ_i) +

δ_iu ln(r²δ_iu) =

u=2

∑

ln r

- δi lnr + (1/r - δ_i)ln(1 - rδ_i) + 2

δ_iu lnr +

δ_iu lnδ_iu ≥

u=2

(вспомним, что

^∑ δ_iu = δ_i, поэтому последняя сумма в силу неравенства Йенсена

u=2

для функции f(x) = x ln x не меньше - ln(r - 1)δ_i + δ_i ln δ_i)

ln r

≥

+ δi lnr + (1/r - δ_i)ln(1 - rδ_i) - δi ln(r - 1) + δi lnδ_i ≥

(воспользуемся тем, что ln(1 - rδ_i) > (-rδ_i)/(1 - rδ_i))

(

)

ln r

≥

+ δi lnδ_i + δi ln

-δ_i.

(23)

r-1

Оценим величину cE_i(Υ) сверху. Выпишем сперва ее как функцию от величин δ_iu,

u = 1,...,r:

[

∑

⁽s⁾

cE_i(Υ) =

k - sh

(1 - q)²

u=1 s=j+1

h=0

t=0

]

)h+t (

)_s-t (

)_k-h-s

⁽1

(r - 1)

-ε_iu

+ε_iu

- q²/r

r²

[

)_s-t

∑

∑ (k-s)(s)

⁽1

δh+t

-δ_i

(1 - q)²

s=j+1

h=0

t=0

(

)_k-h-s

∑

∑ (k-s)(s)

r-1

-δ_i

u=2 s=j+1

h=0

t=0

]

)h+t

)_k-h-s

⁽1

⁽r-2

-δ_iu

δ^s-t

+δ_iu

- q²/r .

(24)

Выражение в правой части (24) содержит две группы вложенных сумм. Их можно

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

и для случая плохих строк.

Утверждение 4. Если r,k,j ∈ N таковы, что 1 < k - j < k1/4, r > 2 и k

достаточно велико по отношению к r, то для любой хорошей или плохой строки

с номером i выполнено следующее неравенство:

)_s-t (

)_k-h-s

∑

∑ (k-s)(s)

h+t

⁽1

r-1

δ_i

-δ_i

≤

s=j+1

h=0

t=0

(

)

≤ q(1 - rδ_i)2j+2-k

1 + δ_iO(k7/12)

/r.

Утверждение 5. Если r,k,j ∈ N таковы, что 1 < k - j < k1/4, r > 2 и k

достаточно велико по отношению к r, то для любой хорошей или плохой строки

с номером i выполнено следующее неравенство:

)h+t

)_k-h-s

∑∑k

∑

∑ (k-s)(s)(1

⁽r-2

s-t

-δ_iu

δ_i

+δ_iu

≤

u=2 s=j+1

h=0

t=0

≤ q(rδ_i)2j+2-kk9(k-j-1)/4(1 + 2/k)²/r.

Доказательства утверждений 4 и 5 мы приведем в § 6. А сейчас воспользуемся

ими и продолжим анализ хороших строк.

С помощью утверждений 4 и 5, а также неравенства c < ln r/q (см. условие (5))

получаем из (24) следующую оценку величины cE_i(Υ):

[

ln r

(

)

cE_i(Υ) ≤

(1 - rδ_i)2j+2-k

1 + δ_iO(k7/12)

r(1 - q)²

]

+ (rδ_i)2j+2-kk9(k-j-1)/4(1 + 2/k)² .

(25)

Теперь оценим разность H_i(Υ) - cE_i(Υ).

(

)

(

)

ln k

Случай 1. Пусть сначала rδ_i >

. Так как δ_i = O

, то δ_i lnδ_i = O

rk2/3

ln r

Значит, в силу (23) при достаточно большом k выполнено H_i(Υ) ≥ 0,85

Далее, раз rδ_i ≤ k-2/3, то для всех достаточно больших k выполнено rδ_i <

Оценим сразу остаточные члены в (25):

δ_ik7/12 ≤ k-1/12,

(

)

(rδ_i)2j+2-kk9(k-j-1)/4(1 + 2/k)² = O

k-2/3(2j+2-k)k9(k-j-1)/4

= k-4/3k+O(k1/4) < 0,0001

для всех достаточно больших k. Следовательно, верна следующая оценка:

[

]

ln r

cE_i(Υ) ≤

(1 - rδ_i)2j+2-k(1 + O(k-1/12)) + 0,0001 .

r(1 - q)²

Далее, заметим, что (1-rδ_i)2j+2-k ≤ (1-1/(3k))2j+2-k ≤ e-(1/3)(2j+2-k)/k. С учетом

того, что (2j+2-k)/k = 1+O(k-3/4), для всех достаточно больших k можно считать,

что (1 - rδ_i)2j+2-k ≤ 1,05e-1/3. Наконец, для всех достаточно больших k выполнено

(1 - q)² < 0,9. В итоге получаем, что

10 lnr[

]

ln r

cE_i(Υ) ≤

1,05e-1/3 + 0,0001

≤ 0,84

Итак, верна оценка

ln r

H_i(Υ) - cE_i(Υ) ≥

(26)

100r

Случай 2. Пусть теперь rδ_i ≤

. Опять начнем с оценивания H_i(Υ). С учетом

неравенства δ_i ≥ r-2k/3 и (23) выполнено

)

(

)

ln r

⁽2k

H_i(Υ) ≥

ln r - ln

δ_i.

r-1

Теперь оценим cE_i(Υ). Воспользуемся тем, что для m ∈ N и x ∈ [0,

] выполнено

неравенство

(1 - x)^m ≤ 1 -

≤1-

mx.

1 + mx

Тогда

(1 - rδ_i)2j+2-k ≤ 1 -

(2j + 2 - k)rδ_i.

Далее, 2j + 1 - k > 9(k - j - 1)/4 > 2, и мы знаем, что rδ_i ≤ 1/(3k). Значит,

(rδ_i)2j+2-kk9(k-j-1)/4 ≤ rδ_i(rδ_ik)2j+1-k ≤ rδ_i(1/3)9(k-j-1)/4 <

rδ_i.

(27)

Кроме того, для всех достаточно больших k выполнено (1 + 2/k)² ≤ 2. Стало быть,

в силу (25)

]

[(

ln r

)(

)

cE_i(Υ) ≤

(2j + 2 - k)rδ_i

1 + δ_iO(k7/12)

+ rδ_i

r(1 - q)²

Остается оценить величину q, участвующую в знаменателе. По определению имеем

(

)

∑

⁽k⁾

q=r1-k

(r - 1)^k-s ≤ 2

r1-k(r - 1)k-j+1 ≤

j+1

s=j+1

(

)

≤2

r2-j ≤ 2kk-j-1r2-j ≤ kk1/4 r2-k+k1/4 ≤ r-k/6rδ_i.

(28)

j+1

Здесь мы воспользовались доминированием слагаемого при s = j+1 в сумме, а также

тем, что k - j < k1/4, а δ_i ≥ r-3k/4. Следовательно,

(1 - q)-2 ≤ 1 + 8q ≤ 1 + 8r-k/6rδ_i,

и значит,

]

[(

ln r

)(

)

cE_i(Υ) ≤

(2j + 2 - k)rδ_i

1 + δ_iO(k7/12)

+ rδ_i (1 + 8r-k/6rδ_i) =

[

]

ln r

(2j + 2 - k)rδ_i + rδ_i + 8r-k/6rδ_i + δ_iO(k7/12)

[

]

ln r

(2j + 2 - k) ln r - ln r - 8r-k/6 ln r + O(k7/12) ln r/r δ_i.

Таким образом,

)

(

)

ln r

⁽2k

H_i(Υ) - cE_i(Υ) ≥

ln r - ln

δ_i -

r-1

[

]

ln r

−

(2j + 2 - k) ln r - ln r - 8r-k/6 ln r + O(k7/12) ln r/r δ_i =

(

)

(2j + 2 - k) ln r + O(k7/12) ln r/r -

ln r δ_i.

В силу того, что k - j < k1/4 и k достаточно велико, выполнено соотношение

ln r

(2j + 2 - k) ln r + O(k7/12) ln r/r -

ln r =

k ln r + O(k7/12)

k ln r.

В итоге для каждой хорошей строки получаем

H_i(Υ) - cE_i(Υ) ≥

k(ln r)δ_i ≥

k(ln r)r-2k/3.

(29)

Отметим, что данная оценка также верна и для предыдущего случая, когда выпол-

нено rδ_i > 1/(3k).

4.3. Плохие строки. Будем называть строку с номером i плохой, если нашелся u₀

с условием εiu0 >

-r-2k/3 и это максимальный элемент среди ε_iu. Вновь для

r²

простоты будем считать, что u₀ = 1. Тогда, пользуясь уже введенными обозначени-

ями δ_i, δ_iu, получаем, что δ_i < r-2k/3. Значит, можно считать, что krδ_i < 1/3.

Оценим H_i снизу так же, как и для хороших строк; полученная оценка (23) верна

всегда:

)

ln r

( r

H_i(Υ) ≥

+ δi lnδ_i + ln

δ_i - δ_i.

r-1

Оценим cE_i(A) сверху. Пользуясь (25), имеем

[

ln r

(

)

cE_i(A) ≤

(1 - rδ_i)2j+2-k

1 + δ_iO(k7/12)

r(1 - q)²

]

+ (rδ_i)2j+2-kk9(k-j-1)/4(1 + 2/k)³

(пользуемся тем, что (1 - rδ_i)2j+2-k = 1 - r(2j + 2 - k)δ_i + O(k²r²δ2i), а также (27)

для оценки последнего слагаемого)

[

]

ln r

1 - r(2j + 2 - k)δ_i + O(k7/12δ_i) =

r(1 - q)²

(используем оценки δ_i < r-2k/3 и (1 - q)-2 = (1 + O(q)), а также q = O(k7/12r-2k/3)

в силу (28))

[

]

ln r

1 - r(2j + 2 - k)δ_i + O(k7/12r-2k/3) (1 + O(q)) =

ln r

- (2j + 2 - k)(ln r)δ_i + O(k7/12r-2k/3).

Получим

)

( r

H_i(Υ) - cE_i(Υ) ≥ δ_i lnδ_i + ln

δ_i - δ_i + (2j + 2 - k)(lnr)δ_i + O(k7/12r-2k/3).

r-1

Минимум данного выражения достигается при δ_i =

, а само выражение при

r2j-k+3

таком δ_i равно

r-1

+ O(k7/12r-2k/3).

r2j-k+3

Значит, либо H_i(Υ) - cE_i(Υ) ≥ 0, либо |H_i(Υ) - cE_i(Υ)| = O(k7/12r-2k/3).

§ 5. Перебор случаев

Мы уже показали в (21), (29), что если плохих строк нет, то найдется такая

функция b = b(k, r), что выполняется искомое неравенство:

∑

G_c(J_r) - G_c(A) ≥

H_i(Υ) - c E_i(Υ) ≥ b∥ε∥².

i=1

5.1. Не только плохие строки. Пусть теперь имеется некоторое количество плохих

строк, но есть дополнительно либо хорошие, либо центральные. Предположим для

удобства, что при i = 1, . . . , s у нас получились плохие строки, а остальные не

являются плохими. Пусть также максимальные элементы плохих строк лежат по

диагонали, они обязаны находиться в разных столбцах в силу свойств матрицы A.

Тогда согласно результатам предыдущего параграфа

∑

H_i(A) ≥ c E_i(A) - O(sk7/12r-2k/3).

i=1

Случай 1. Пусть имеется центральная строка с номером i₀ > s. Тогда все эле-

менты нормированной матрицы A/n в первых s столбцах будут меньше r-2k/3 ≤

≤ r-23-2/3, ведь они лежат в одном столбце с 1/r - δ_u, u = 1, . . . , s. Но эти эле-

менты равны

+ εi0u, u = 1, . . ., s. Значит, εi0u отрицательны и, более того, εi0u <

r²

< (3-2/3 - 1)r-2. Но тогда согласно (21)

∑

r²

Hi0 (Υ) - cEi0 (Υ) ≥

ε2i

≥

s(3-2/3 - 1)²r-4 ≥

r-2.

u: εi₀u<0

Полученная оценка значительно больше, чем O(sk7/12r-2k/3), при достаточно боль-

шом k. Значит, при наличии центральной строки имеем G_c(A) - G_c(J_r) ≥

r-2,

и этого более чем достаточно в наших условиях.

Случай 2. Если же центральных строк нет, но среди оставшихся есть хорошая с

номером i₀, то запаса разницы между Hi0 (A) и cEi0 (A) снова более чем достаточ-

но, чтобы компенсировать плохие строки. Согласно (29) данная разность не мень-

ше

k(ln r)r-2k/3, что при k ≥ k₀(r) значительно больше, чем O(sk7/12r-2k/3) =

= O(rk7/12r-2k/3).

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

все строки матрицы A являются плохими.

5.2. Только плохие строки. Наконец, пусть в каждой строке нормированной мат-

рицы A/n имеется элемент, лежащий в пределах [1/r-r-2k/3, 1/r]. Подобные элемен-

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

∑

Обозначим их, как и раньше, через 1/r - δ_i, i = 1, . . ., r. Тогда для

H_i(Υ) снова

(

)

∑

i=1

используем оценку (23). А вот величину c ln 1 + E_i(Υ) в (20) будем оценивать

i=1

целиком, чтобы получить более точные оценки. Обозначим

∑

ψ = (1 - q)²

E_i(Υ).

i=1

Из (24) имеем

[

)_s-t

∑

∑ (k-s)(s)

⁽1

h+t

ψ=

δ_i

-δ_i

i=1

s=j+1

h=0

t=0

(

)_k-h-s

∑

∑ (k-s)(s)

r-1

-δ_i

u=i s=j+1

h=0

t=0

]

)h+t

)_k-h-s

⁽1

⁽r-2

-δ_iu

δs-tiu

+δ_iu

- q²/r .

100

Будем рассматривать коэффициенты при степенях δ_i и δ_iu до второй. Сразу от-

метим, что минимальная степень при δ_iu равна 2j + 2 - k, а это сильно больше двух.

Свободный член (коэффициент при нулевой степени δ_i) равен

(

)

∑

∑ (k⁾⁽1)s (r - 1)k-s

- q²/r

i=1

s=j+1

(

)

∑

⁽k⁾

r^-k

(r - 1)^s - q²/r

= (q/r - q²/r) = q - q².

i=1

s=j+1

i=1

Коэффициент при первой степени равен

[

∑

⁽k)(

)

s(r - 1)^k-s + (k - s)(r - 1)k-s-1

rk-1

i=1

s=j+1

]

∑

⁽k⁾

s(r - 1)^k-s +

(k - s)(r - 1)k-1-s δ_i =

s=j+2

s=j+1

(

)

∑

= -r1-k

(j + 1)(r - 1)k-j-1

δ_i.

j+1

i=1

С учетом ограничений на δ_i ∈ [0, r-2k/3] степени по δ_i и δ_iu выше первой (с учетом

коэффициентов) будут составлять O(qk²δ2i) = O(qk²r-4k/3) (см. утверждения 4 и 5),

а значит, будет выполнено соотношение

(

)

∑

ψ=q-r1-k

(j + 1)(r - 1)k-j-1

δ_i - q² + O(qk²r-4k/3).

j+1

i=1

Доминирующим слагаемым здесь будет q = O(kk-j-1r2-j) (см. (28)). Отсюда полу-

чаем, что

( ∑r

)

(

)

c ln

1 + E(Υ)

= cln

(1 - q)²

i=1

(

)

+ O(q³)

(1 - q)²

Далее, заметим, что

ψ(1 - q)-2 = ψ(1 + 2q + O(q²)) =

(

)

∑

=q-r1-k

(j + 1)(r - 1)k-j-1 δ_i + q² + O(qk²r-4k/3).

j+1

i=1

В свою очередь,

(

)

∑ )

k-j-1

ψ²(1 - q)-4 = q² + O qr1-k

(j + 1)(r - 1)

δ_i

j+1

i=1

= q² + O(qk^k-jr1-j-2k/3).

101

Стало быть,

(∑r

)

c ln

E_i(Υ)

i=1

(

)

∑

k-j-1

=c q-r1-k

(j + 1)(r - 1)

δ_i + q²/2 + O(qk²r-4k/3)

j+1

i=1

∑

С учетом нижней оценки (23) для H_i(Υ) нам достаточно взять такое c, что

i=1

[(

(

)

∑

ln r

min

1-r1-k

(j + 1)(r - 1)k-j-1

δ_i/q +

δi∈[0,r-2k/3]

j+1

i=1

)-1(

[

])]

∑

)

( r

δ_i

+ O(k²r-4k/3)

δ_i log_r δ_i + log_r

δ_i -

r-1

ln r

i=1

Нам важен порядок этого минимума с точностью до o(q/ lnr). Снова используя

оценки на δ_i, получаем, что

(

)

)-1

∑

k-j-1

1-r1-k

(j + 1)(r - 1)

δ_i/q +

+ O(k²r-4k/3)

j+1

i=1

( ∑r

[

])

)

( r

δ_i

× 1+

δ_i log_r δ_i + log_r

δ_i -

r-1

ln r

i=1

(пользуемся тем, что |δ_i log_r δ_i| = O(kr-2k/3))

(

)

[

r1-k

(r - 1)k-j-1

)

]

∑

( r

j+1

=1+

(j + 1)

δ_i + δ_i log_r δ_i + log_r

δ_i -

r-1

ln r

i=1

+ O(k²r-4k/3).

Обозначим через f(x) следующую функцию:

(

)

1-k

(r - 1)k-j-1

)

j+1

( r

f (x) = (j + 1)

x + xlog_r x + log_r

r-1

ln r

r-1

Минимум значения f(x) достигается при x = x₀ =

, где

rt+1

(

)

1-k

(r - 1)k-j-1

j+1

t = (j + 1)

r-1

Подставляя его, получаем значение f(x₀) = -

. В итоге нам достаточно взять

rt+1 ln r

ln r

r-1

(

)

q-1(lnr)k²r-4k/3

rt+1q

Осталось заметить, что

(

)

(

))

k-j

q=r1-k

(r - 1)k-j-1

1+O

j+1

k(r - 1)

102

Откуда следует, что

(

)

1-k

(r - 1)k-j-1

(

))

j+1

k-j

t = (j + 1)

= (j + 1)

1+O

k(r - 1)

= j + 1 + O((k - j)/r),

а также что

(

)

(

)

(

)k-j-1

k-j

= O rk-1(r - 1)j+1-k

(

)

=O rk-1

(r - 1)k

j+1

r-1

Значит, величину

можно оценить сверху следующим образом: при всех доста-

r^tq

точно больших k > k₀(r) выполнено

(

)

(

)k-j-1

r-1

k-j

r-1

=O rk-1

rt+1q

(r - 1)k

rt+1

(

)

(

)k-j-1

k-j

r-1

=O rk-1

(r - 1)k

rj+1+O((k-j)/r)

((

)k-j-1)

(k - j)r¹⁺O(1/r)

(r - 1)k

((

)k-j-1⁾

r1+O(1/r)

=k4⁽j-k+1)(1+o(1)) ≤ k(j-k+1)/2.

k3/4

Тем самым, лемма 2 полностью доказана.

§6. Доказательства вспомогательных утверждений

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

использованных в статье.

6.1. Доказательство утверждения 1. Рассмотрим по определению

G_c(J_r) = H(J_r) + cE(J_r) = -r²

+ cln(1 - Q(J_r)) = lnr + cln(1 - Q(J_r)).

r²

Теперь вычислим Q(J_r). В силу (14)

∑

∑ (k-s)(s)

Q(J_r) = 2q -

i,u=1 s=j+1

h=0

)h+t (

)_s-t (

t=0)_k-h-s

⁽1

r-2

r²

Проверим, что кратная сумма в правой части равна q². Действительно, простыми

преобразованиями получаем

)h+t (

)_s-t (

)_k-h-s

∑

∑ (k-s)(s)(1

(r - 1)²

r²

s=j+1

h=0

t=0

103

∑

∑ (k-s)(s)

⁽k⁾

=r-2k

(r - 1)^k-s

(r - 1)k-s-h+t =

s=j+1

h=0

t=0

(сделаем замену s^′ = s + h - t вместо t)

)

∑

⁽k⁾

∑ (k - s⁾⁽ s

=r-2k

(r - 1)^k-s

(r - 1)k-s′ =

s^′ - h

s=j+1

h=0 s^′=j+1

∑

∑ (k-s)(s)

⁽k⁾

=r-2k

(r - 1)^k-s

(r - 1)k-s′

s^′ - h

s=j+1

s^′=j+1

h=max(0,s^′-s)

∑

⁽k⁾

q²

=r-2k

(r - 1)^k-s

(r - 1)k-s′ =

s^′

r²

s=j+1

s^′=j+1

Суммирование по i, u дает недостающий множитель r². В итоге Q(J_r) = 2q - q² и

G_c(J_r) = lnr + c ln(1 - q)². Утверждение 1 доказано.

6.2. Доказательство утверждения 3. Сначала оценим величину q. Напомним, что

∑

q=r1-k

⁽k)(r-1)k-s. В силу условия s ≥ j+1 > k/2 максимальное слагаемое

s=j+1

соответствует значению s = j + 1, поэтому

(

)

q≤r1-kk

(r - 1)k-j-1 ≤ r1-kk(kr)k-j-1 =

k-j-1

= r^-k(kr)^k-j ≤ r^-kek1/4(lnk+lnr).

(30)

Видно, что при всех достаточно больших k данная величина очень мала. В частно-

сти, можно считать, что q < 1/2.

Докажем первое неравенство. В силу вышеприведенной оценки q получаем

qr²2^k lnr

≤ 4qr²2^k lnr ≤ 4r²2^k lnrr^-kek1/4(lnk+lnr) ≤

(1 - q)²

(пользуемся тем, что r > 2)

≤ 4r²2^k ln r3^-kek1/4(lnk+lnr) = r²(2/3)k+O(k1/4 lnk) <

Последнее неравенство верно при всех достаточно больших k по отношению к r.

Докажем второе неравенство. Пользуясь оценкой (30), имеем

(

qr^k lnr 1-

)-2e-k1/3

)-2

k2/3

≤ 4qr^k lnr

e-k1/3 ≤

(1 - q)²

k2/3

(

)-2

≤ 4ek1/4(lnk+lnr) lnr

e-k1/3 = e-k1/3+O(k1/4 lnk) ln r < e-10r ln r

k2/3

для всех k, достаточно больших по отношению к r. Утверждение 3 доказано.

6.3. Доказательство утверждения 4. Рассмотрим цепочку преобразований

)_s-t (

)_k-h-s

∑

∑ (k-s)(s)

⁽1

r-1

h+t

δ_i

-δ_i

s=j+1

h=0

t=0

104

∑

∑ (k-s)(s)

=r^-k

(rδ_i)h+t(1 - rδ_i)^s-t(r - 1 - rδ_i)^k-h-s ≤

s=j+1

h=0

t=0

(выделим отдельно члены суммы при t = h = 0 и t > h = 0 и оценим грубо множи-

тель (1 - rδ_i)^s-t, учитывая, что s - t ≥ 2j + 2 - k в силу (13))

[

∑

⁽k⁾

≤ r^-k(1 - rδ_i)2j+2-k

(r - 1 - rδ_i)^k-s +

s=j+1

∑

⁽s⁾

(rδ_i)^t(r - 1 - rδ_i)^k-s +

s=j+2

t=1

]

∑

∑ (k-s)(s)

(rδ_i)h+t(r - 1 - rδ_i)k-h-s

(31)

s=j+1

h=1

t=0

Во всех суммах множитель вида (r - 1 - rδ_i)^α оценим сверху выражением (r - 1)^α.

∑

Тогда первая сумма оценится величиной

⁽k)(r-1)k-s = rk-1q. Далее, во

)

s=j+1

⁽s

⁽k-s⁾

второй и третьей суммах

оценим сверху через k^t, а

≤ (k - s)^h ≤ kh/4.

В итоге выражение (31) не превосходит

[

∑

r^-k(1 - rδ_i)2j+2-k rk-1q +

k^t(rδ_i)^t(r - 1)^k-s +

s=j+2

t=1

]

∑

kt+h/4(rδ_i)h+t(r - 1)k-h-s

(32)

s=j+1

h=1

t=0

Далее мы рассмотрим два случая в зависимости от того, насколько велико значе-

ние krδ_i.

Случай 1. Пусть krδ_i > 2. Оценим сначала первую сумму в скобках в (32). В ней

∑

воспользуемся тем, что

k^t(rδ_i)^t ≤ 2(krδ_i)s-j-1. Тогда

t=1

∑

⁽k⁾

k^t(rδ_i)^t(r - 1)^k-s ≤ 2

(r - 1)^k-s(krδ_i)s-j-1 =

s=j+2

t=1

s=j+2

∑

⁽k⁾

= 2krδ_i

(r - 1)^k-s(krδ_i)s-j-2 ≤

s=j+2

(воспользуемся тем, что для хорошей или плохой строки выполнено rδ_i ≤ k-2/3)

∑

⁽k⁾

≤ 2krδ_i

(r - 1)^k-sk(s-j-2)/3.

s=j+2

Оценим отношение последовательных слагаемых в получившейся сумме:

⁽k⁾

(s-j-2)/3

(r - 1)^k-sk

k1/3(k - s + 1)

k7/12

(

)

≤

≤k-5/12,

s(r - 1)

(k - k1/4)(r - 1)

(r - 1)k-s+1k(s-j-3)/3

s-1

105

начиная с некоторого k. Здесь мы воспользовались тем, что s ≥ j + 1 > k - k1/4

и r > 2. В итоге, сворачивая геометрическую прогрессию и пользуясь неравенством

(1 - x)-1 ≤ 1 + 2x при x = k-5/12, получаем, что первая сумма в скобках (32)

не превосходит

(

)

2krδ_i(r - 1)k-j-2

(1 + 2k-5/12) =

j+2

(

)

(

)

= 2krδ_i(r - 1)-1 ( j+2)

(r - 1)k-j-1(1 + 2k-5/12) =

j+1

(

)

k-j-1

= 2krδ_i(r - 1)-1

(r - 1)k-j-1(1 + 2k-5/12) ≤

j+2

j+1

(

)

(воспользуемся тем, что

(r - 1)k-j-1 < qrk-1)

j+1

(k - j)k

≤ 2qr^k

(33)

δ_i (j + 2)(r - 1)(1+2k-5/12)(1+2k-5/12)=O(qrkδⁱk1/4r-1)

в силу условия j ∼ k и k - j < k1/4.

∑

Аналогично оценим вторую сумму в скобках в (32). Сумму

(krδ_i)^t по t

t=0

оценим как удвоенное максимальное слагаемое, т.е. как 2(krδ_i)s-j-1+h. В итоге ис-

комая сумма не превосходит

∑

kh/4(rδ_i)^h(r - 1)^k-h-s2(krδ_i)s-j-1+h =

s=j+1

h=1

∑

⁽k⁾

∑

(r - 1)^k-s(krδ_i)s-j-1

(k5/4r²δ2i(r - 1)-1)^h.

s=j+1

h=1

Заметим, что k5/4r²δ2i(r-1)-1 < k5/4-4/3 = k-1/12, а потому сумма по h оценивается

сверху своим максимальным слагаемым (при h = 1), умноженным на 1 + 2k-1/12.

Стало быть, получаем оценку

∑

⁽k⁾

ks-j-1+5/4(rδ_i)s-j+1(r - 1)k-s-1(1 + 2k-1/12).

s=j+1

Снова рассмотрим отношение соседних слагаемых в оставшейся сумме по s:

⁽k⁾

k-s-1

ks-j-1+5/4(rδ_i)s-j+1(r - 1)

(k - s + 1)krδ_i

(

)

≤

s(r - 1)

ks-j-2+5/4(rδ_i)^s-j(r - 1)^k-s

s-1

1/4+1-2/3

≤

≤k-5/12.

(k - k1/4)(r - 1)

Следовательно, сумма по s оценивается сверху своим максимальным слагаемым

(при s = j + 1), умноженным на 1 + 2k-5/12. В итоге получаем оценку

(

)

2(rδ_i)²

k5/4(r - 1)k-j-2(1 + 2k-1/12)(1 + 2k-5/12) ≤

j+1

106

(снова воспользуемся тем, что rδ_i ≤ k-2/3)

(

)

≤ 2rδ_i

k7/12(r - 1)k-j-2(1 + 2k-1/12)(1 + 2k-5/12) ≤

j+1

(

)

(применим очевидное неравенство

(r - 1)k-j-1 < qrk-1)

j+1

≤ 2r^kqδ_ik7/12(r - 1)-1(1 + 2k-1/12)(1 + 2k-5/12) = O(r^kqδ_ik7/12r-1).

(34)

В итоге из (33) и (34) получаем, что в рассматриваемом случае выражение (32) не

превосходит

[

]

r^-k(1 - rδ_i)2j+2-k

rk-1q + O(rk-1qδ_ik1/4) + O(rk-1qδ_ik7/12)

(

)

= q(1 - rδ_i)2j+2-kr-1

1 + O(δ_ik7/12)

Случай 2. Пусть теперь krδ_i ≤ 2. Вновь отдельно оценим суммы, входящие в (32).

Начнем с первой. Внутреннюю сумму по t оценим тривиальным образом, пользуясь

∑

ограничением второго случая:

(krδ_i)^t ≤ krδ_i2s-j-1. Стало быть,

t=1

∑

∑ (k⁾

(krδ_i)^t(r - 1)^k-s

≤ krδ_i

(r - 1)^k-s2s-j-1.

s=j+2

t=1

s=j+2

Покажем, что в получившейся сумме максимальному слагаемому отвечает s = j+2.

Рассмотрим отношение последовательных слагаемых в сумме:

⁽k⁾

s-j-1

(r - 1)^k-s2

2(k - s + 1)

2k1/4

(

)

≤

≤ 2k-3/4,

s(r - 1)

(r - 1)(k - k1/4)

(r - 1)k-s+12s-j-2

s-1

начиная с некоторого k, где переход в неравенстве выполнен с учетом убывания

выражения по s и ограничения k - s < k1/4. Значит, вся сумма оценивается своим

максимальным слагаемым, умноженным на 1 + 4k-3/4:

(

)

∑

⁽k⁾

krδ_i

(r - 1)^k-s2s-j-1 ≤ 2

krδ_i(r - 1)k-j-2(1 + 4k-3/4) =

j+2

s=j+2

(

)

(

)

= 2krδ_i(r - 1)-1(1 + 4k-3/4

(

)

(r - 1)k-j-1 ≤

j+1

(

)

(пользуемся тем, что

(r - 1)k-j-1 ≤ qrk-1)

j+1

(

)

(k - j - 1)k

≤ 2qr^kδ_i(1 + 4k-3/4)

=O qrk-1δ_ik1/4

(35)

(j + 2)(r - 1)

Здесь мы снова пользовались тем, что j ∼ k и k - j < k1/4.

Остается оценить вторую сумму в (32). Здесь все полностью аналогично. Внут-

ренняя сумма по t оценивается с помощью ограничения krδ_i ≤ 2:

∑

(krδ_i)^t ≤ 2s-j+h.

t=0

107

Следовательно,

∑

kt+h/4(rδ_i)h+t(r - 1)^k-h-s ≤

s=j+1

h=1

t=0

∑

≤

kh/4(rδ_i)^h(r - 1)^k-h-s2s-j+h =

s=j+1

h=1

∑

⁽k⁾

⁽2k1/4rδ_i )^h

(r - 1)^k-s2^s-j

r-1

s=j+1

h=1

Сумма по h - это снова геометрическая прогрессия, причем ее знаменатель мал: из

условия rδ_i ≤ k-1 получаем, что

2k1/4rδ_i

≤k-3/4.

r-1

Значит, вся сумма оценивается сверху своим первым слагаемым, умноженным на

1 + 2k-3/4. В итоге имеем оценку

∑

2k1/4r

⁽k⁾

δ_i(1 + 2k-3/4)

2^s-j(r - 1)k-s-1.

r-1

s=j+1

Проверим, что в оставшейся сумме максимальному слагаемому отвечает s = j + 1.

Вновь выпишем отношение последовательных членов суммы:

⁽k⁾

k-s-1

2^s-j(r - 1)

2(k - s + 1)

(

)

≤ 2k-3/4,

s(r - 1)

2s-j-1(r - 1)^k-s

s-1

тогда вся сумма оценивается своим максимальным слагаемым, умноженным на

1 + 4k-3/4. Получаем итоговую оценку:

∑

2k1/4r

⁽k⁾

δ_i(1 + 2k-3/4)

2^s-j(r - 1)k-s-1 ≤

r-1

s=j+1

(

)

2k1/4r

≤

δ_i(1 + 2k-3/4)

2(r - 1)k-j-2(1 + 4k-3/4) ≤

r-1

j+1

(

)

(пользуемся тем, что

(r - 1)k-j-1 ≤ qrk-1)

j+1

≤ 4k1/4qr^k(r - 1)-2δ_i(1 + 2k-3/4)(1 + 4k-3/4) = O(qr^kk1/4r-2δ_i).

(36)

В итоге, из (35) и (36) получаем, что выражение (32) не превосходит

[

]

r^-k(1 - rδ_i)2j+2-k rk-1q + O(qrk-1δ_ik1/4) + O(qr^kk1/4r-2δ_i) =

(

)

= q(1 - rδ_i)2j+2-kr-1

1 + O(k1/4δ_i)

Утверждение 4 доказано.

108

6.4. Доказательство утверждения 5. Преобразуем оцениваемое выражение:

)h+t

)_k-h-s

∑∑k

∑

∑ (k-s)(s)(1

⁽r-2

s-t

-δ_iu

δ_i

+δ_iu

u=2 s=j+1

h=0

t=0

∑

∑ (k-s)(s)

=r^-k

u=2 s=j+1

h=0

t=0

× (1 - rδ_iu)h+t (rδ_iu)^s-t (r - 2 + rδ_iu)^k-h-s .

Здесь достаточно совсем грубых оценок. Оценим биномиальные коэффициенты сле-

дующим образом:

⁽s⁾

⁽k - s⁾

≤k^t,

≤ (k - s)^h ≤ (k1/4)^h.

В последнем неравенстве мы пользуемся тем, что k - s < k - j < k1/4. Отметим

также, что раз rδ_i < k-2/3 < 1, то r - 2 + rδ_iu < r - 1. Далее, в силу (13) выполнено

s-t ≥ 2j +2-k, а потому (rδ_iu)^s-t ≤ (rδ_iu)2j+2-k. Стало быть, искомое выражение

не превосходит величины

∑

r^-k (rδ_iu)2j+2-k

(r - 1)^k-h-s

kk-s+t+h/4.

u=2

s=j+1

h=0

t=0

Внутренняя сумма по t - это геометрическая прогрессия с растущим знаменателем k,

потому она не превосходит своего последнего слагаемого, умноженного на 1 + 2/k.

Получаем оценку

∑

r^-k (rδ_iu)2j+2-k

(r - 1)^k-h-skk-j-1+5h/4(1 + 2/k) ≤

u=2

s=j+1

h=0

∑

⁽k⁾

≤ r^-kkk-j-1 (rδ_iu

)2j+2-k

(r - 1)^k-s

k5h/4(1 + 2/k) ≤

u=2

s=j+1

h=0

∑

⁽k⁾

≤ r^-kkk-j-1 (rδ_iu

)2j+2-k

(r - 1)^k-sk5(k-s)/4(1 + 2/k)².

u=2

s=j+1

Здесь мы снова воспользовались оценкой геометрической прогрессии. Применим

оценку k5(k-s)/4 ≤ k5(k-j-1)/4, тогда оставшаяся сумма по s станет равна qrk-1.

В итоге получаем оценку

∑

qr-1k9(k-j-1)/4(1 + 2/k)²

(rδ_iu)2j+2-k.

u=2

∑

Осталось заметить, что в силу условий δ_iu ≥ 0 и

δiu = δi выполнено простое

неравенство для норм:

u=2

(∑r

)2j+2-k

∑

2j+2-k

δ2j+2-k

≤

δ_iu

=δ_i

u=2

Утверждение 5 доказано.

109

СПИСОК ЛИТЕРАТУРЫ

Cutler J., Radcliffe A.J. Hypergraph Independent Sets // Combin. Probab. Comput. 2013.

V. 22. № 1. P. 9-20. https://doi.org/10.1017/S0963548312000454

Ordentlich E., Roth R.M. Independent Sets in Regular Hypergraphs and Multidimensional

Runlength-Limited Constraints // SIAM J. Discrete Math. 2004. V. 17. № 4. P. 615-623.

https://doi.org/10.1137/S0895480102419767

Балобанов А.Е., Шабанов Д.А. О числе независимых множеств в простых гипергра-

фах // Матем. заметки. 2018. Т. 103. № 1. С. 38-48 https://doi.org/10.4213/mzm11508

Семенов А.С., Шабанов Д.А. Независимые множества общего вида в случайных сильно

разреженных гиперграфах // Пробл. передачи информ. 2018. Т. 54. № 1. С. 63-77.

http://mi.mathnet.ru/ppi2260

Heckel A. The Chromatic Number of Dense Random Graphs // Random Structures Algo-

rithms. 2018. V. 53. № 1. P. 140-182. https://doi.org/10.1002/rsa.20757

Shabanov D.A. Estimating the r-Colorability Threshold for a Random Hypergraph // Dis-

crete Appl. Math. 2020. V. 282. P. 168-183. https://doi.org/10.1016/j.dam.2019.10.031

Ширяев А.Н. Вероятность. В 2-х кн., 6-е изд. испр. М: МЦНМО, 2017.

Schmidt-Pruzan J., Shamir E., Upfal E. Random Hypergraph Coloring Algorithms and

the Weak Chromatic Number // J. Graph Theory. 1985. V. 9. № 3. P. 347-362. https:

//doi.org/10.1002/jgt.3190090307

Schmidt J.P. Probabilistic Analysis of Strong Hypergraph Coloring Algorithms and the

Strong Chromatic Number // Discrete Math. 1987. V. 66. № 3. P. 259-277. https://doi.

org/10.1016/0012-365X(87)90101-4

10.

Shamir E. Chromatic Number of Random Hypergraphs and Associated Graphs // Ran-

domness and Computation. Adv. Comput. Res. V. 5. Greenwich, CT: JAI Press, 1989.

P. 127-142.

11.

Krivelevich M., Sudakov B. The Chromatic Numbers of Random Hypergraphs // Random

Structures Algorithms. 1998. V. 12. № 4. P. 381-403. https://doi.org/10.1002/(SICI)

1098-2418(199807)12:4<381::AID-RSA5>3.0.CO;2-P

12.

Dyer M., Frieze A., Greenhill C. On the Chromatic Number of a Random Hypergraph //

J. Combin. Theory Ser. B. 2015. V. 113. P. 68-122. https://doi.org/10.1016/j.jctb.

2015.01.002

13.

Ayre P., Coja-Oghlan A., Greenhill C. Hypergraph Coloring up to Condensation // Random

Structures Algorithms. 2019. V. 54. № 4. P. 615-652. https://doi.org/10.1002/rsa.20824

14.

Achlioptas D., Kim J.H., Krivelevich M., Tetali P. Two-Colorings Random Hypergraphs //

Random Structures Algorithms. 2002. V. 20. № 2. P. 249-259. https://doi.org/10.1002/

rsa.997

15.

Achlioptas D., Moore C. On the 2-Colorability of Random Hypergraphs // Random-

ization and Approximation Techniques in Computer Science (Proc. 6th Int. Workshop

RANDOM’2002. Cambridge, MA, USA. Sept. 13-15, 2002). Lect. Notes Comput. Sci.

V. 2483. Berlin: Springer, 2002. P. 78-90. https://doi.org/10.1007/3-540-45726-7_7

16.

Coja-Oghlan A., Zdeborová L. The Condensation Transition in Random Hypergraph 2-Col-

oring // Proc. 23rd Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA’12). Kyoto,

Japan. Jan. 17-19, 2012. P. 241-250. https://doi.org/10.1137/1.9781611973099.22

17.

Coja-Oghlan A., Panagiotou K. Catching the k-NAESAT Threshold // Proc. 44th Annu.

ACM Symp. on Theory of Computing (STOC’12). New York, USA. May 19-22, 2012.

P. 899-908. https://doi.org/10.1145/2213977.2214058

18.

Семенов А.С. Двухцветные раскраски случайного гиперграфа // Теория вероятн. и ее

примен. 2019. Т. 64. № 1. С. 75-97. https://doi.org/10.4213/tvp5165

19.

Balobanov A.E., Shabanov D.A. On the Strong Chromatic Number of a Random 3-Uniform

Hypergraph // Discrete Math. 2021. V. 344. № 3. Paper No. 112231 (16 pp.). https:

//doi.org/10.1016/j.disc.2020.112231

110

20. Semenov A.S., Shabanov D.A. On the Weak Chromatic Number of Random Hypergraphs //

Discrete Appl. Math. 2020. V. 276. P. 134-154. https://doi.org/10.1016/j.dam.2019.

03.025

21. Hatami H., Molloy M. Sharp Thresholds for Constraint Satisfaction Problems and Ho-

momorphisms // Random Structures Algorithms. 2008. V. 33. № 3. P. 310-332. https:

//doi.org/10.1002/rsa.20225

Семенов Александр Сергеевич

Поступила в редакцию

Московский физико-технический институт

09.03.2020

(государственный университет),

После доработки

факультет инноваций и высоких технологий,

18.02.2022

кафедра дискретной математики

Принята к публикации

alexsemenov1992@mail.ru

18.02.2022

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

Московский физико-технический институт

(государственный университет),

лаборатория комбинаторных и геометрических структур

Московский государственный университет

им. М.В. Ломоносова, механико-математический факультет,

кафедра теории вероятностей

Национальный исследовательский университет

«Высшая школа экономики»,

факультет компьютерных наук

dmitry.shabanov@phystech.edu

111