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

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