Кнезеровский граф

Кнезеровский граф [math]\displaystyle{ KG_{n,k} }[/math] — это неориентированный граф, описывающий отношение непересекаемости [math]\displaystyle{ k }[/math]-элементных подмножеств [math]\displaystyle{ n }[/math]-элементного множества друг с другом.

Формальное определение

Пусть [math]\displaystyle{ R_n=\{1,2,\cdots,n\} }[/math]. Тогда кнезеровский граф [math]\displaystyle{ KG_{n,k}=(V,E) }[/math] определяется как пара множеств вершин [math]\displaystyle{ V=\{S \mid S \subset R_n, |S|=k\} }[/math] и рёбер [math]\displaystyle{ E=\{(A,B) \mid A \in V, B \in V, A \cap B = \varnothing\} }[/math]

Частные случаи

При [math]\displaystyle{ k \gt \frac{n}{2} }[/math] кнезеровский граф является пустым графом (без рёбер).

При [math]\displaystyle{ k = \frac{n}{2} }[/math] кнезеровский граф представляет собой паросочетание. Конечно, рассматривается только случай [math]\displaystyle{ n \equiv 0\pmod{2} }[/math]

При [math]\displaystyle{ k=1 }[/math] кнезеровский граф является полным графом.

Граф [math]\displaystyle{ KG_{5,2} }[/math] является графом Петерсена.

Основной интерес представляют кнезеровские графы со значениями параметра [math]\displaystyle{ k }[/math] в промежутке [math]\displaystyle{ [2;\frac{n}{2}) }[/math].

Хроматическое число

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

Общие тривиальные оценки

Числом независимости [math]\displaystyle{ \alpha (G) }[/math] называется размер максимально независимого множества вершин в графе [math]\displaystyle{ G }[/math]. Определение раскраски означает, что [math]\displaystyle{ \alpha (G) }[/math] определяет максимальное количество вершин, которое можно покрасить в один цвет. Исходя из некоторой модификации принципа Дирихле, хроматическое число графа можно оценить как [math]\displaystyle{ \chi (G) \ge \frac{|V|}{\alpha (G)} }[/math]

Аналогично определяется кликовое число [math]\displaystyle{ \omega (G) }[/math] как размер максимальной клики. Это число даёт оценку [math]\displaystyle{ \chi (G) \ge \omega (G) }[/math]

Как правило, первая оценка лучше второй — а именно, для случайного графа [math]\displaystyle{ G }[/math] на [math]\displaystyle{ n }[/math] вершинах вероятность того, что [math]\displaystyle{ \alpha (G) \lt 2\log_2{n} }[/math] стремится к единице с растущим [math]\displaystyle{ n }[/math]. Из того, что каждой клике графа [math]\displaystyle{ G }[/math] можно сопоставить независимое множество графа [math]\displaystyle{ \not G }[/math], можно заключить, что то же самое верно для [math]\displaystyle{ \omega (G) }[/math].

Однако кнезеровский граф даёт наглядную иллюстрацию целого класса графов, дискредитирующих изложенные выше оценки (в общем случае, а не для случайных графов).

Кликовое число

Не ограничивая общности предположим, что [math]\displaystyle{ \{1,\dots,k\} }[/math] входит в клику как вершина. Тогда, из определения клики, ни одна другая вершина не должна содержать в своём подмножестве ни один элемент из [math]\displaystyle{ \{1,\dots,k\} }[/math]. При дальнейшем аналогичном анализе это очевидным образом даёт [math]\displaystyle{ \omega (KG_{n,k})= \left \lfloor \frac{n}{k} \right \rfloor }[/math]

Число независимости

Из комбинаторных соображений очевидно, что [math]\displaystyle{ \alpha (KG_{n,k}) \ge \binom{n-1}{k-1} }[/math]. Для построения независимого множества такого размера достаточно зафиксировать одну вершину и перебрать все [math]\displaystyle{ k }[/math]-элементные подмножества, содержащие её. По определению, между любой парой таких множеств не будет ребра.

Эрдёш, Ко и Радо в 1961 году опубликовали доказательство теоремы, утверждающей равенство в изложенной выше оценке. По словам математиков, они нашли доказательство ещё за несколько десятилетий до этого, но в то время его не имело смысла публиковать, потому что теорема была никому неинтересна. К слову, граф Кнезера в то время ещё не был известен, так что Эрдёш, Ко и Радо доказывали теорему в элементарной формулировке максимального количества попарно пересекающихся [math]\displaystyle{ k }[/math]-элементных подмножеств [math]\displaystyle{ n }[/math]-элементного множества.

Пользуясь тривиальной оценкой, из данного значения числа независимости можно получить только [math]\displaystyle{ \chi (KG_{n,k}) \ge \frac{\binom{n}{k}}{\binom{n-1}{k-1}}=\frac{n}{k} }[/math], то есть [math]\displaystyle{ \chi (KG_{n,k}) \ge \left \lceil \frac{n}{k} \right \rceil }[/math]. Эта оценка почти не отличается от оценки через кликовое число.

Точное значение

Сформулированная в 1955 году Мартином Кнезером и доказанная в 1977 году Ласло Ловасом теорема утверждает, что [math]\displaystyle{ \chi (KG_{n,k})=n-2k+2 }[/math]

Построение оптимальной раскраски

Для любого [math]\displaystyle{ j=1,2,\ldots, n-2k+1 }[/math] покрасим в [math]\displaystyle{ j }[/math]-й цвет каждое подмножество, минимальным элементом которого является число [math]\displaystyle{ j }[/math]. Покрасим в цвет [math]\displaystyle{ n-2k+2 }[/math] каждое подмножество, содержащиеся в множестве [math]\displaystyle{ \{n-2k+2,n-2k+3,\ldots ,n\} }[/math]. Так как в указанном множестве [math]\displaystyle{ 2k-1 }[/math] элемент, то любые два его [math]\displaystyle{ k }[/math]-элементных подмножества пересекаются, то есть между соответствующими вершинами нет ребра. Значит, построенная раскраска правильная.

См. также

Источники

Научно-популярный физико-математический журнал "Квант", 2011 год, "Гипотеза Кнезера и топологический метод в комбинаторике" (А. Райгородский)