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

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

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

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

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

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

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

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

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

Числом независимости ${\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}$-элементных подмножества пересекаются, то есть между соответствующими вершинами нет ребра. Значит, построенная раскраска правильная.

• Раскраска графов
• Хроматическое число
• Клика (теория графов)
• Независимое множество (теория графов)

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