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

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

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

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

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

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

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

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

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

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

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