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

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

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

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

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

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

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

При $k=1$ кнезеровский граф является полным графом.

Граф $KG_{5,2}$ является графом Петерсена.

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

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

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

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

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

Аналогично определяется кликовое число $\omega (G)$ как размер максимальной клики. Это число даёт оценку $\chi (G)\geq \omega (G)$

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Источники

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