Кнезерів граф

Кнезерів граф $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 рік, «Гіпотеза Кнезера і топологічний метод у комбінаториці» (А. Райгородський)