Независимые множества

Множество вершин гиперграфа называется независимым, если оно не содержит ребер. Пустое множество вершин по определению независимо. Как и в случае графов, наибольшее по мощности независимое множество вершин гиперграфа Н называется наибольшим, а число вершив вэтом множестве называется числом независимости гиперграфа Н и обозначается через αо(Н). Через ГН обозначается множество, элементами которого служат все независимые множества вершин гиперграфа Н.

Очевидно, что изучая независимые множества вершин гиперграфе, естественно рассматривать гиперграфы без кратных ребер. Опишем, как каждому такому гиперграфу поставить в соответствие монотонную булеву функцию. Пусть Н — гиперграф, VH =(1,2, ..., п), x_v=( х₁,х₂, ..., х_п) — характеристический вектор произвольного подмножества U € VH. Определим булеву функцию f_H, Положив f_H (x)=0 для n-мерного (0, 1)-вектора х = х_v Тогда и только тогда, когда U € ГH. Поскольку любое подмножество независимого множества также независимо, то функция f_H монотонна и f_n (0, 0, ..., 0) = 0.

Соответствие Н -> f_H не является, вообще говоря, инъективным, поскольку ребра гиперграфа могут содержаться одно в другом. Поэтому определенный интерес представляют гиперграфы специального вида — антицепи. Гиперграф называется антицепью, если никакое из его ребер в является подмножеством другого ребра. Очевидно, что все k-однородные гиперграфы и, в частности, все простые графы — антицепи.

Пусть Н — произвольная антицепь с непустым мно­жеством ребер, VH = {1, 2, ..., п). Очевидно, что харак­теристические векторы ребер гиперграфа Н попарно не­сравнимы относительно порядка ≤: x=( х₁, х₂, ..., х_п)≤ y=( y₁, y₂, ..., y_п) <=> (x_i ≤ y_i i = 1, п). Поэтому суще­ствует единственная монотонная булева функция п пере­менных, множество нижних единиц которой совпадает с множеством всех характеристических векторов ребер ги­перграфа H. Очевидно, что f_H и есть такая функция. Для антицепи, не имеющей ребер, f_H = 0.

С другой стороны, пусть f — монотонная булева функ­ция п переменных, f ≠ 1. Определим гиперграф H_f, поло­жив VH_f = {1, 2, ..., п) и объявив ребрами все подмно­жества в VH_f, характеристические векторы которых слу­жат нижними единицами функции f_H. Поскольку эта функ­ция монотонна, то гиперграф H_f окажется антицепью. Очевидно, что f_{H f} = f.

Итак, соответствие f -> H_f — биекция между мно­жеством монотонных булевых функций, отличных от тож­дественно равной 1, и множеством антицепей.

Здесь X — столбец неизвестных x₁, x₂ ,.. ,x_n, В — стол­бец высоты m с неотрицательными элементами. Нас бу­дут интересовать (0, 1)-решения этой системы. Определим булеву функцию f п переменных, положив f(x₁, x₂ ,.. ,x_n) = 0 тогда и только тогда, когда (x₁, x₂ ,.. ,x_n) — решение системы (1). Очевидно, что f — монотонная функ­ция и f (0, 0, ..., 0) = 0. Скажем, что функция f задается системой неравенств (1).

Очевидно, что вектор х = x_U = (x₁, x₂ ,.. ,x_n) — решение этой системы тогда и только тогда, когда U € SH. Последнее означает, что f_{H f} = 0. Но f_Hf = f , следовательно, функция f задается системой (2).

Если же антицепь H_i не имеет ребер, т. е. если f=0, то в качестве системы неравенств (2) можно взять си­стему x_i ≤ 1 (i = 1, п).

Очевидно, что система неравенств, задающая монотон­ную булеву функцию, определяется неоднозначно.

Из всего сказанного выше очевидно вытекает сле­дующее

Утверждение 69.1. Пусть f — монотонная булева функция, отличная от тождественно равной 1, (1)—за­дающая эту функцию система линейных неравенств, H_f — соответствующая антицепь, VH_f = (1, 2, ...,п), U € VH_f, x_U — характеристический вектор подмножества U. Тогда следующие высказывания эквивалентны:

1) f (x_U)=0;

2) вектор x_U является решением системы (1);

3) U€ГH_f.

Для того частного случая, когда все нижние единицы функции f имеют норму 2 (функция f графическая), ука­занная связь между функциями, системами неравенств и антицепями отмечалась ранее в § 28. В этой и только в этой ситуации антицепь H_f является простым графом.

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

Раскраски

Так же, как для графов, вводится понятие вершинной раскраски гиперграфов. Раскраска вершин гиперграфа Н называется правильной, если любое ребро е = EH содер­жит две вершины, окрашенные в различные цвета. Ясно, что правильную раскраску могут допускать лишь гипер­графы, каждое ребро которых имеет степень не меньше чем 2. В этом параграфе рассматриваются только такие типерграфы. Кроме того, будем считать, что изолирован­ных вершин гиперграф не содержит.

Гиперграф называется k-раскрашиваемым (k-цветным), если для него существует правильная раскраска в k цветов.

Хроматическое число χ(H) — это наименьшее число цветов, достаточное для правильной раскраски гиперграфа Н. Если χ(Н)=k, то гиперграф Н называется к-хроматическим.

Очевидно, что разбиению множества VH на независи­мые множества S₁, S₂, ..., S_k соответствует правильная раскраска вершин гиперграфа Н k цветами. Верно, конечно, и обратное утверждение.

где αо(Н)— число независимости гиперграфа Н.

Отсюда сразу получаем χ(Н)+ α_о(Н)> 2√п

Далее, пусть S — наибольшее независимое множество вершин гиперграфа Н. Окрасим все вершины из S в один цвет и используем п — |S| = п — α_о(Н) других цветов для окрашивания всех вершин из V \ S в разные цвета» В результате получаем χ(Н) + а_о(Н)≤ п+ 1.

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

Абсолютным гиперграфом будем называть гиперграф для любых двух вершин и и v которого существует ребра е = uv. Оказывается, справедлива следующая теорема, яв­ляющаяся обобщением теоремы Брукса (§ 54).

Теорема 70.2 (Л. Ловас, 1968 г.). Если Н — связ­ный гиперграф, отличный от абсолютного, и Δ(Н) ≥ 3, то χ(H)≤(Н).

Порядком d_H (v) вершины v гиперграфа Н называется мощность наибольшего подмножества E' €EН, |E’| ≥ 2, для любых двух различных ребер е' в е" которого е' ∩ е" = {v}. Если такого подмножества не существует, то по определению d_H(v)= 1.

Доказательства двух предыдущих теорем опускаем. Если |Si| = 1 ( i = 1, k), то учитывая очевидное нера­венство Δ(Н)≥ d(H), где d(H)= max d_H(v), получаем

Следствие 70.4. Для любого гиперграфа Н верно неравенство

χ(H) ≤ d(H)+1.

Отсюда сразу имеем (ср. со следствием 54.2) Следствие 70.5. Для любого гиперграфа Н верно неравенство

χ(H) ≤ Δ(H)+1

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

Теорема 70.6. Для любых целых чисел k ≥ 1 и h ≥ 2 существует такой гиперграф Н, что χ(Н)≥ k и |е| ≥ h для любого ребра е € EH.

В качестве такого гиперграфа можно взять h-однородный гиперграф Н, построенный по следующему прави­лу: VH = {v₁, v₂, ..., v_n} где n ≥ k(h — 1), ЕH — семей­ство всевозможных подмножеств множества VH мощности h. Поскольку а_о(Н) ≤ h— 1, то на основании теоре­мы 70.1 χ(H)≥n/(h-l), т. е. χ(H)≥ k.

Более сильный результат приведем без доказательства.

Теорема 70.7 (П. Эрдёш, А. Хайнал, 1966 г.). Для любых целых чисел h, k, l≥2 существует h-однородный k-хроматический гиперграф, который не содержит циклов длины меньше l.

Известно, какую роль в теории графов играют бихроматические графы, т. е. графы, хроматическое число которых не превосходит 2. Простой, но очень важный критерий бихроматичности графа дал Д. Кёниг: граф не должен со­держать циклов нечетной длины.

Гиперграф Н тоже будем называть бихроматическим, если χ(H)≤2. Для гиперграфа пока не найдено крите­рия бихроматичности в терминах его структуры.

Доказательство проводим по той же схеме, что и доказательство теоремы 9.1, предполагая, что гиперграф

связен. А именно, сначала окрасим произвольную верши­ну v гиперграфа Н в красный цвет, затем произвольную вершину и, отличную от v, окрасим в красный цвет, если расстояние d(u, v) — четное число, и в синий цвет, если это расстояние нечетно. Если Н — не бихроматический гиперграф, то найдутся две смежные вершины и и w, ок­рашенные в один цвет, а тогда легко обнаруживается цикл нечетной длины.

Как показывает пример гиперграфа, изображенного на рис. 70.1, условие утверждения 70.8 не являются необхо­димыми.

Более широкий класс бихроматических графов нашли Фурнье и Лас Верньяс. Этот результат приведем без до­казательства.

Теорема 70.9 (Ж. Фурнье, М. Лас Верпьяс, 1972). Если в каждом цикле нечетной длины гиперграфа Н есть три ребра, имеющие общую инцидентную вершину, то гиперграф Н является бихроматическим.

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

Непосредственно из теоремы Кёнига следует

Утверждение 70.10. Если гиперграф является бихроматическим, то он не содержит ни одного цикла нечетной длины, состоящего лишь из ребер степени 2.

Пример гиперграфа, изображенного на рис. 70.2, пока­зывает, что обратное утверждение неверно.

Доказательства теорем, опущенные в этом парагра­фе, можно найти в [20].