Рекуррентные верхние оценки в задаче Эрдеша-Хайнала о раскраске гиперграфа и в ее обобщениях

Настоящая работа посвящена известной проблеме экстремальной теории гиперграфов, которая восходит к П. Эрдешу и А. Хайналу.

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

В 1961 году Эрдеш и Хайнал заметили (см. [1]), что если у n-однородного гиперграфа не слишком много ребер (например, не больше, чем 2 “ ^-1 ), то вершины этого гиперграфа допускают раскраску в два цвета, при которой все ребра гиперграфа неодноцветны (содержат вершины обоих цветов). Это мотивировало их к рассмотрению величины m(n), равной наименьшему m G N, такому, что существует n-однородный гиперграф с m ребрами, вершины которого нельзя раскрасить в два цвета с соблюдением условия неодноцветности всех ребер.

Следуя, опять же, Эрдешу и Хайналу, можно сказать еще и так: гиперграф обладает свойством B , если найдется раскраска множества его вершин в два цвета, при которой все его ребра неодноцветны; тогда

m(n) = min {| E | : H = (V, E) — n-однородный гиперграф, H не обладает свойством B } .

Сейчас известно, что

°'¹ ( li nn У/ 2 2 “ <  m(n) <  e(ln2)n ² 2 “ ^-2 (1 + o(1)).                    (1)

Нижняя оценка принадлежит Дж. Радхакришнану и А. Сринивасану (см. [2]), а верхняя — Эрдешу (см. [3]).

Настоящая работа выполнена при финансовой поддержке гранта РФФИ № 12-01-00683.

Одно из наиболее естественных обобщений величины m(n) было предложено А. М. Райгородским и Д. А. Шабановым в 2003 году (см. [4]). А именно, скажем, что гиперграф обладает свойством Bk , если его вершины можно так покрасить в два цвета, чтобы каждое его ребро содержало не меньше k вершин первого цвета и не меньше k вершин второго цвета. Разумеется, если гиперграф n-однороден, то к С 22. Соответственно mk(n) = min{|E|: H = (V, E) — n-однородный гиперграф, H не обладает свойством Bk}.

Понятно, что m 1 (n) = m(n).

Поскольку величина m k (n) зависит от двух параметров, устроена она сложнее, нежели ее классическая предшественница. К настоящему времени известно довольно много разных оценок для m k (n), и их подробный обзор можно найти в статье [5] (см. также [6]). В данной работе нас будут интересовать верхние оценки, их мы здесь и приведем.

В сущности, есть всего два результата, и оба они были получены Шабановым (см. [4, 7]):

mk(n) С mk-1(n — 1) С ... С m(n — к + 1) С eln2(n — к + 1)22n k+1(1 + о(1)), mk(n) С eln2 n2k-2---(1 + o(1)), k = о lnnn . (2)

E СП i=0

Конечно, первый результат с ростом n гораздо слабее второго. Более того, при конкретных («малых») значениях величин k и n оба результата совсем не применимы, ведь в них никак не конкретизируется вид функции о (1).

В принципе аналогичная проблема возникает и в связи с верхней оценкой из соотношения (1). Этой проблеме был посвящен ряд работ, в которых были получены явные рекуррентные оценки для величины m ( n ).

Во-первых, Х. Аббот и Л. Мозер показали (см. [8]), что m(ab) С m(a)(m(b))a.                                   (3)

Поскольку равенства m(2) = 3, m(3) = 7 очень просты, утверждение Аббота-Мозера позволяет делать явные оценки и для других значений параметров. При этом асимптотически оно гораздо слабее (1).

Во-вторых, Аббот и Д. Хансен установили (см. [9]) неравенства

m(n) С m(n — 2)n + 2 ^{n -} 1 , n = 2k + 1, m(n) С m(n — 2)n + 2 ^n-1 + 2 ^n- 2 , n = 2k, m(n) С (2n — 1)(m(n — 2) + 1).

Наконец, Б. Тофт доказал (см. [10]) оценку для четных n :

m(n) С m(n — 2)n + 2 ^n-1 + 2 C ^/ ² .                         (4)

Все перечисленные оценки по-своему важны. Например, из результатов Аббота–Мозера вытекает неравенство m(4) С 27, которое Аббот-Хансен улучшают до m(4) С 24, а Тофт — до m(4) С 23; последний факт есть текущий рекорд, который, по-видимому, усилить нельзя (хотя известно лишь, что m(4) ^ 17). В то же время Аббот-Мозер показывают, что m(6) С 147, тогда как, по Абботу-Хансену,

m(6) С 6m(4) + 32 + 16 С 186, m(6) С 11(m(4) + 1) С 264, а по Тофту, m(6) С 180.

В случае свойства B _k подобный результат — это приведенный выше результат Шабанова m k (n) С m k - i (n — 1) С ... С m(n — к + 1), поскольку теперь мы можем применять к нему рекурсии Аббота–Мозера, Аббота–Хансена или Тофта. Других результатов такого типа не было. Известно лишь, что конкретно m 2 (4) = 4, m 2 (5) = 7, m 3 (7) С 8 и m ₄ (9) С 8 (см. [11]).

Нам удалось получить рекуррентные соотношения непосредственно для величин m k (n). Идеологически наши результаты близки к результатам Аббота–Мозера и Тофта. Соответственно в разделе 2 мы приведем оценки, которые служат в некотором смысле обобщениями неравенства (3); в разделе 3 мы сформулируем результаты типа (4). В разделе 4 мы обсудим оценку (2) и поймем, что она тоже может быть сделана явной (т.е. устраним функцию o(1) из нее). В разделе 5 мы проведем детальный анализ соотношений между оценками из разделов 2–4 и выпишем в итоге наилучшие из полученных нами неравенств для m k (n) при некоторых малых n и к. Наконец, в разделе 6 мы докажем все новые теоремы.

В заключение отметим, что проблематика, возникшая за полвека с момента постановки Эрдешем и Хайналом задачи про m(n), крайне обширна и разнообразна. Обзор многочисленных результатов в этой области может быть найден в статьях [6] и [12].

• 2.    Обобщение идеи Аббота–Мозера

• 3.    Обобщение идеи Тофта

В своей работе [8] Аббот и Мозер применили принцип, основанный на копировании одного гиперграфа, не обладающего свойством B , и своего рода объединении всех копий, в результате которого получаются ребра большей длины. Для объединения использовался второй гиперграф, также не обладающий свойством B . Мы действуем похожим методом, объединяя одинаковые гиперграфы, не обладающие свойством B k , при помощи гиперграфа, не обладающего свойством B l . В итоге возникает

Теорема 1. Для любых натуральных к, 1 и a ^ 2к, b ^ 21 выполнено:

m ai+bk - ki+k+i - a - b (ab) С m k (a)(m i (b)) ^a .                             (5)

В частности, при 1 = к = 1 мы возвращаемся к неравенству (3) Аббота-Мозера. В параграфе 6.1 мы докажем теорему 1.

В работе [10] Тофта используется идея «склейки» так называемых критических ги-перграфов. Желая обобщить эту идею, введем понятие B _k -критического гиперграфа, то есть такого гиперграфа H = (V, E), что он связен и не обладает свойством B k , но любой гиперграф, получающийся из него выбрасыванием ребра, обладает этим свойством. В нижеследующем утверждении 1 мы приведем пример гиперграфа, не обладающего свойством B k . А в утверждении 2 мы предъявим B k -критический гиперграф.

Утверждение 1. Пусть n,1 — натуральные числа, причем n ^ 2 , а 1 С П 2 • Рассмотрим множество вершин V l = { x 1 ,..., x _2l-1 , a 1 ,..., a n , b 1 ,..., b n } и множество ребер E l , состоящее из таких ребер A, что A = { x 1 ,..., x _2l-1 , a i , b i } , i E { 1,..., n — 1 + 1 }, или A = { c 1 ,..., c n - l+1 , a _n-l+ 2 ,..., a n } , где c i = a i или c i = b i . Подчеркнем, что гиперграф H l = (V l , E l ) имеет 2n + 21 — 1 вершин, n — 1 + 1 ребер размера 21 + 1 и 2 ^n-l+1 ребер размера n. Тогда гиперграф H l = (V l ,E l ) не обладает свойством B l .

Утверждение 1 — аналог утверждения, сформулированного Тофтом в [10], и в нем построен гиперграф, не обладающий свойством B i с некоторым l (l C 22 ).

Утверждение 2. Пусть n,l — натуральные числа, причем l C 2 . Рассмотрим гиперграф H i = (V i ,E i ), у которого V = { У 1 ,У 2 ,... ,У п ,Х 1 ,Х 2 ,... ,X 2i - 1 } и A € E i , если и только если A = { x ₁ , x ₂ ,..., x _2i-1 , y i } , i = 1, 2,..., n — l + 1 , или A = { y ₁ , y ₂ ,..., y n }. Этот гиперграф является B l -критическим.

Утверждения мы докажем в параграфах 6.3 и 6.4, а пока сформулируем с их помощью теорему, которая позволит нам получить оценки для величины m k (n). Справедлива

Теорема 2. Зафиксируем натуральные числа n, k, l с условиями n ^ 2 , k ^ l и l C n . Пусть Н ₁ и H 2 — два непересекающихся гиперграфа, причем Н ₁ — произвольный гиперграф, не обладающий свойством B _k , а H ₂ — произвольный гиперграф, не обладающий свойством B _l , из утверждения 1 (утверждения 2) с соответствующими параметрами n, l . Рассмотрим гиперграф H , полученный следующим образом:

V(H ) = V(H 1 ) и (V(H 2 ) \ { Х 1 ,..., Х 2І - 1 } )),

E(H ) = (E (H \{ x 1 ,...,X 2i - 1 } )) U

U { A | A = A i U B j , A i € E (H 1 ), B j U{ x 1 ,..., x^ } € E№) } .

Тогда гиперграф H не обладает свойством B k .

Из формулировки теоремы видно, что из нее можно извлекать оценки для величины m k (n). Однако для получения таких оценок нужно подсчитать общее число ребер итогового гиперграфа. Ниже мы получим следствия, в которых будут указаны явные рекуррентные формулы.

Следствие 1. Имеет место оценка:

m _k (n) C m k (n — 2) • (n — k + 1) + 2 ^n-k+1 .                       (6)

Доказательcтво следствия 1. Воспользуемся теоремой 2. В качестве гиперграфа H ₁ возьмем любой (n — 2)-однородный гиперграф с m k (n — 2) ребрами, не обладающий свойством B k . Тогда H 1 , очевидно, B k -критический. В качестве гиперграфа H 2 возьмем гиперграф из утверждения 1.

Заметим, что гиперграф H , получаемый с помощью конструкции из теоремы 2, n-однороден. Ввиду теоремы 2 он не обладает свойством B k . В то же время | E(H) | = = | E(H ₁ ) | • (n — l + 1) + 2 ^n-i+1 . Значит, m k (n) <  m k (n — 2) • (n — l + 1) + 2 ^n-i+1 . Замечая, что по условию теоремы 2 выполнено неравенство l C k, и подставляя l = k, получаем искомую оценку. Следствие доказано. >

Следствие 2. Имеет место оценка mk(n) < mk (n — 1) • (n — k + 1) + 1.                          (7)

Доказательство следствия 2. Воспользуемся теоремой 2. В качестве гиперграфа H 1 возьмем любой (n — 1)-однородный гиперграф с m k (n — 1) ребрами, не обладающий свойством B _k . Тогда H ₁ , очевидно, B _k -критический. В качестве гиперграфа H ₂ возьмем гиперграф из утверждения 2.

Заметим, что гиперграф H , получаемый с помощью конструкции из теоремы 2, n-однороден. Ввиду теоремы 2 он не обладает свойством B k . В то же время | E(H) | = = | E(H ₁ ) | • (n — l + 1) + 1. Значит, m k (n) C m k (n — 1) • (n — l + 1) + 1. Подставляя l = k, получаем искомое неравенство. Следствие доказано. >

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

• 4.    Оценки с помощью систем общих представителей

Оценка (2) была получена с помощью так называемых систем общих представителей (с.о.п.). Напомним основные определения. Пусть Kn = {1,..., n} — множество, состоящее из n элементов. Пусть, далее, M = {M1,..., Ms} — совокупность любых подмножеств Kn. Положим k = min |Mi|. Рассмотрим произвольное множество S С Kn, обладающее тем i=1,...,s свойством, что S П Mj = 0 для каждого j Е {1,..., s}. Такое множество S называется системой общих представителей (с.о.п.) для совокупности M. Положим

Z(n, s, k) = maxmin {| S | : S является с.о.п. для M } .

M

В данных обозначениях сформулируем теорему, которая и позволит нам получать верхние оцнеки для m k (n).

Теорема 3. Пусть v Е N, n Е N, к Е N с условиями n < 2, k ^ n. Тогда при k-1

a = Cn , b = min V (CП-j • Cj_x + Cj • Cn-) , c = 2 v               x vx x vx j=0

имеем mk (n) ^ min Z(a,c, b). v

Доказательство этой теоремы приведено в статье [7] Д.А. Шабанова и не будет приводиться здесь. Неравенство (2) получается из теоремы 3 и следующего утверждения, в котором дается явная оценка величины Z(n, s, k).

Теорема 4. Для любых n, s, k имеет место неравенство

Z(n, s, k) <  max/ ⁿ , ⁿ In sk 1 + ⁿ + 1.

, ,                 _k , _{k n k}

Доказательство теоремы 4 приведено в книге [13] А.М. Райгородского и в данной статье не приводится. Оценка из теоремы 4 при конкретных (малых) значениях параметров n, s, k допускает небольшое уточнение. Опишем алгоритм построения системы общих предста- вителей, дающий и саму оценку, и ее уточнение.

Зафиксируем совокупность M = {M1,..., Ms}. Возьмем такой элемент v1 Е Kn, что количество множеств из M , которые его содержат, максимально. Это будет первый эле- мент с.о.п. Нетрудно видеть, что он служит представителем для не менее sk n

множеств

из M . Значит, непредставленными остались s 1 ^ s —

sk n

множеств, причем все они на-

ходятся в K n \ { v 1 } = K _n-1 . Продолжая процедуру, берем элемент v ₂ Е K _n-1 , который

принадлежит не менее совокупность M .

^s 1 k

n — 1

множествам M . И так далее, покуда не исчерпаем всю

В дальнейшем, строя наилучшим образом оценки для m k (n) с помощью систем общих представителей, мы перебираем все возможные значения величины v из теоремы 3, для каждого из таких значений берем параметры a, b, c и оцениваем Z (a, c, b) с помощью описанного «жадного» алгоритма. Эти расчеты осуществляются на компьютере.

• 5.    Сопоставление результатов

В нашей работе мы получили рекуррентные соотношения (5), (6), (7). Кроме того, мы знаем оценку Шабанова mk(n) C mk-1(n - 1) C ... C m(n — k + 1)                       (8)

и метод получения оценок с помощью с.о.п. Попытаемся сравнить все эти результаты между собой. Рассмотрим k = 2, 3 и n C 10.

Напомним, что m(2) = 3, m(3) = 7, m(4) C 23, m(6) C 147 (см. введение). Заметим, что, исходя из неравенств, выписанных во введении, m(5) C 51, m(7) C 421, m(8) C 1339, m(9) C 2401, m(10) C 7803. Также из введения мы знаем, что в работе [11] получены соотношения m ₂ (4) = 4, m ₂ (5) = 7, m ₃ (7) C 8, m ₄ (9) C 8. Наконец, равенство m ₃ (6) = 3 очевидно.

Посмотрим на неравенство (5). В нем есть параметры k, l ∈ N. Первый из них может путаться с индексом величины m k (n). Поэтому переобозначим его через к. Ясно, что величины κ, l не равны одновременно единице, т.к. в этом случае мы возвращаемся к величине m(n). Пусть сперва к = 1, 1 = 2. Мы знаем, что а ^ 2к, b ^ 21, т.е. а ^ 2, b ^ 4. Сама оценка имеет вид m _a + ₁ (ab) C m(a)(m ₂ (b)) ^a . Нас интересуют только числа k = 2, 3 и n = ab C 10, поэтому либо а = 2, b = 4, либо а = 2, b = 5, и видно, что при k = 2 оценка не работает. Если теперь к = 2, 1 = 1, то опять k ^ 3 ив нужных нам ситуациях либо а = 4, b = 2, либо а = 5, b = 2. В итоге получаем m ₃ (8) C 48 и m ₃ (10) C 147.

Пусть теперь k = 2. Случаи n C 5, как мы помним, изучены ранее. Пусть, стало быть, n ^ 6. Неравенство (5) не применимо, а неравенства (6), (7), (8) и метод с.о.п. работают. Их и сравним. Имеем m2(6) C m2 (4) • 5 + 25 = 52 (неравенство (6)), m2(6) C m2(5) • 5 + 1 = 36 (неравенство (7)), m2 (6) C m(5) C 51 (неравенство (8)), m2(6) C 66 (метод с.о.п.).

Видим, что в данном случае оценка (7) сильнее всех.

Теперь подсчитаем m 2 (7) по тем же формулам:

m ₂ (7) C m ₂ (5) • 6 + 2 6 = 106 (неравенство (6)), m ₂ (7) C m ₂ (6) • 6 + 1 C 217 (неравенство (7)), m 2 (7) C m(6) C 147 (неравенство (8)), m ₂ (7) C 182 (метод с.о.п.).

Здесь сильнее всех оценка (6).

Аналогично действуем для n = 8, 9,10:

m2 (8) C m2 (6) • 7 + 27 C 380 (неравенство (6)), m2 (8) C m2 (7) • 7+1 C 743 (неравенство (7)), m2(8) C m(7) C 421 (неравенство (8)), m2(8) C 468 (метод с.о.п.), m2 (9) C m2 (7) • 8 + 28 C 1104 (неравенство (6)), m2(9) C m2(8) • 8 + 1 C 3041 (неравенство (7)), m2(9) C m(8) C 1339 (неравенство (8)), m2(9) С 1146 (метод с.о.п.), m2(10) С m2(8) • 9 + 29 С 3932 (неравенство (6)), m2(10) С m2(9) • 9 + 1 С 9937 (неравенство (7)), m2 (10) С m(9) С 2401 (неравенство (8)), m2(10) С 2720 (метод с.о.п.).

Видим, что все неравенства, кроме (с.о.п.), в тех или иных ситуациях оказываются наилучшими: для n = 6 — неравенство (7), для n = 7, 8, 9 — неравенство (6), для n = 10 — неравенство (8).

Обратимся к случаю к = 3. Здесь нужно смотреть на n ^ 7, причем при n = 7 неравенство (6) не применимо:

m ₃ (7) С 8 (работа [11]), m ₃ (7) С m ₃ (6) • 5 + 1 = 16 (неравенство (7)), m ₃ (7) С m(5) С 51 (неравенство (8)), m ₃ (7) С 26 (метод с.о.п.), m 3 (8) С 48 (неравенство (5)), m 3 (8) С m 3 (6) • 6 + 2 6 С 82 (неравенство (6)), m 3 (8) С m 3 (7) • 6 + 1 С 49 (неравенство (7)), m 3 (8) С m(6) С 147 (неравенство (8)), m ₃ (8) С 63 (метод с.о.п.), m ₃ (9) С m ₃ (7) • 7 + 2 7 С 184 (неравенство (6)), m 3 (9) С m 3 (8) • 7+1 С 337 (неравенство (7)), m ₃ (9) С m(7) С 421 (неравенство (8)), m ₃ (9) С 150 (метод с.о.п.), m 3 (10) С 147 (неравенство (5)), m 3 (10) С m 3 (8) • 8 + 2 8 С 640 (неравенство (6)), m ₃ (10) С m ₃ (9) • 8 + 1 С 1201 (неравенство (7)), m ₃ (10) С m(8) С 1339 (неравенство (8)), m ₃ (10) С 343 (метод с.о.п.).

При n = 7 известный ранее результат улучшить не удалось, при n = 8,10 и даже при n = 9 лучшим является неравенство (5), ведь m 3 (9) С m 3 (10) С 147.

В заключение приведем таблицу, содержащую наилучшие оценки для величин m k (n) при малых k, n.

k/n	2	3	4	5	6
1	3	7	23	51	147
2	—	—	4, [10]	7, [10]	36, (7)
3	—	—	—	—	3
k/n	7	8	9	10
1	421	1339	2401	7803
2	106, (6)	380, (6)	1104, (6)	2401, (8)
3	8, [10]	48, (5)	147, (5)	147, (5)

Хорошо видно, что все подходы важны. Кажется, что маловато оценок, где (7) сильнее всех, и вовсе нет оценок с превосходством (с.о.п.). В первом случае можно заметить, что, например, m ₂ (8) хоть и оценивается лучше всего за счет (6), но в этой оценке участвует величина m 2 (6), оценка которой, в свою очередь, уже опирается на (7): мы ведь указываем лишь последнюю рекурсию, а не всю предысторию. Что же касается с.о.п., то ясно, что при больших по сравнению с k величинах n они все равно рано или поздно возобладают. А при других соотношениях между k и n «выстрелить» может любое неравенство.

• 6.    Доказательства

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

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

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

Возьмем a-однородный гиперграф H = (V, E), который имеет m k (a) ребер и не обладает свойством B k . Без ограничения общности будем считать, что V = { 1, 2,..., v } . Пусть Н ₁ = (V 1 , E₁) — b-однородный гиперграф с m l (b) ребрами, который не обладает свойством B l . Рассмотрим H t = (V t , E t ), t = 2,..., v, — непересекающиеся по вершинам копии гиперграфа H ₁ . Построим ab-однородный гиперграф H = (V, E) следующим образом. Положим V = UV ₌₁ V i . Пусть h Е E — некоторое ребро гиперграфа H , h = { s ₁ ,..., s _a } . Тогда рассмотрим совокупность E h = { f ₁ U .. . U f a : f i Е E s i ,i = 1,..., a } всевозможных объединений ребер гиперграфов H s ₁ , . . . , H s _a , взятых по одному из каждого гиперграфа. Получается (m i (b)) ^a подмножеств множества V, каждое из которых имеет мощность ab. Наконец, положим E = IJh e E E h . Из построения следует, что H = (V, E ) — ab-однородный гиперграф, у которого m k (a)(m l (b)')^a ребер. Проверим, что он не обладает свойством B _{ai+bk-ki+k+i-a-b} .

Пусть ρ — произвольная раскраска множества V в 2 цвета. Тогда ρ задает двухцветные раскраски на всех множествах V i , i = 1, . . . , v . В силу того, что все H i не обладают свойством B _l , в каждом из гиперграфов найдется ребро, содержащее менее l вершин одного цвета. Такое ребро мы обозначим e _i (если таких ребер несколько, то возьмем любое из них). Рассмотрим следующую раскраску множества V вершин гиперграфа H : вершине i Е V = { 1,..., v } сопоставляем цвет, который «доминирует» в ребре e i (т.е. тот цвет, в который окрашены более чем b — l вершин). Получается некоторая раскраска р множества V в два цвета. В силу того, что H не обладает свойством B k , найдется ребро h o , которое в раскраске р имеет по крайней мере a — к + 1 вершин одного цвета (скажем, «красного»). Из построения множества E h ₀ следует, что ё = Ui e h ₀ e i Е E h ₀ • Как мы знаем, среди ребер e i , входящих в состав ребра ё, есть не менее a — к + 1 ребер, в каждом из которых не менее b — l + 1 вершин красного цвета. Таким образом, мы нашли ребро гиперграфа H , имеющее по крайней мере (a — к + 1)(b — l + 1) вершин одного цвета. Следовательно, наш ab-однородный гиперграф уж точно не обладает свойством B ai+bk - ki+k+i - a - b .

Зафиксируем гиперграф H ₁ , не обладающий свойством B k , и гиперграф H ₂ , не обладающий свойством B _l , из утверждения 1 или 2. Отметим, что доказательства в случаях, когда H 2 из утверждения 1 и когда H 2 из утверждения 2, совпадают. Ниже мы приведем общее рассуждение, верное в случае обоих утверждений.

Предположим, вопреки утверждению теоремы, что гиперграф H , построенный в нем, обладает свойством B _k . Рассмотрим произвольную раскраску р множества вершин V =

= V (H) в 2 цвета. Поскольку H 1 не обладает свойством B k , то при раскраске р множества V (H 1 ) С V (H ) существует ребро A i Е E (H 1 ), в котором не более чем к — 1 вершина покрашена (без ограничения общности) в первый цвет. Далее, вершины из множества V (H 2 ) \ { x 1 ,..., x _2l-1 } также имеют некоторые цвета в раскраске р. Поскольку гиперграф H 2 не обладает свойством B l , у него есть ребро, в котором вершин одного из цветов меньше l. Это ребро может содержать все вершины x ₁ , . . . , x _2l-1 , а может и не содержать ни одной из этих вершин (других ребер в утверждениях 1 и 2 просто нет). Рассмотрим оба случая.

Случай 1. Все ребра гиперграфа H ₂ , не содержащие вершины x ₁ , . . . , x _2l-1 , покрашены правильно (то есть каждое ребро имеет по крайней мере l вершин каждого цвета). Тогда найдется такой набор вершин B j , что B j U { x 1 ,..., x _2l-1 } Е E(H 2 ) и ни одна из вершин B j не покрашена в цвет 1. В самом деле, если это не так, то вершины x ₁ , . . . , x _{l -1} можно покрасить в цвет 1, а вершины x _l , . . . , x _{2 l -1} — в цвет 2 и гиперграф H ₂ оказывается обладающим свойством B l . Возьмем ребро A i U B j гиперграфа H . Оно содержит не более к — 1 вершин цвета 1, что противоречит изначальному предположению о наличии свойства

B k у H .

Случай 2. Существует ребро e Е E(H 2 \ { x 1 ,..., x _2l-1 } ), в котором вершин одного из цветов меньше 1. Тогда, поскольку e Е H , гиперграф H не обладает свойством B i , а следовательно, и свойством B k , ведь к ^ 1. Опять получаем противоречие.

• 6.3.    Доказательство утверждения 1

• 6.4.    Доказательство утверждения 2

Докажем от противного. Пусть H l все же обладает свойством B l . Тогда заметим, что в правильной раскраске существуют две возможности: либо ровно 1 — 1 вершина среди x 1 ,... x _2l-1 покрашена в один из цветов и 1 вершин — в другой, либо 1 — 2 вершины покрашены в один цвет и 1 + 1 вершин — в другой. Очевидно, в обоих случаях среди ребер { c 1 ,... c _n-l+1 , a n - l+2 , ..., a n } , где c i = a i или c i = b i , найдется ребро, содержащее по крайней мере n — 1 + 1 вершин одного цвета, а значит, вершин другого цвета — не более 1 — 1. Противоречие.

Докажем от противного. Пусть H l все же обладает свойством B l . Тогда заметим, что в каждом ребре A = { x 1 , x ₂ ,..., x _2l-1 , y i } , i = 1, 2,..., n — 1 + 1, все y i покрашены в один и тот же цвет, но тогда в ребре A = { y 1 , y ₂ ,..., y _n } , очевидно, найдется n — 1 + 1 вершин одного цвета, а значит, вершин другого цвета не больше 1 — 1. Противоречие.

Гиперграф H l является критическим. Доказательство этого факта очевидно.