Граф Кнезера

Граф Кнезера
Граф Кнезера K (5, 2) , изоморфный графу Петерсена
Назван в честь	Мартин Кнезер
Вершины	${\displaystyle {\binom {n}{k}}}$
Края	${\displaystyle {\frac {1}{2}}{\binom {n}{k}}{\binom {nk}{k}}}$
Хроматическое число	${\displaystyle {\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}}$
Характеристики	${\displaystyle {\tbinom {nk}{k}}}$-регулярный дуго-транзитивный
Обозначение	К ( н , к ), КГ н , к .
Таблица графиков и параметров

В теории графов граф Кнезера K ( n , k ) (альтернативно KG _{n , k} ) — это граф , вершины которого соответствуют k -элементным подмножествам множества из n элементов , и где две вершины являются смежными тогда и только тогда, когда два соответствующих множества не пересекаются . Графы Кнезера названы в честь Мартина Кнезера , который впервые исследовал их в 1956 году.

Граф Кнезера K ( n , 1) — это полный граф на n вершинах.

Граф Кнезера K ( n , 2) является дополнением линейного графа полного графа на n вершинах.

Граф Кнезера K (2 n − 1, n − 1) является нечетным графом O _n ; в частности, O ₃ = K (5, 2) является графом Петерсена (см. верхний правый рисунок).

Граф Кнезера O ₄ = K (7, 3) , изображенный справа.

Граф Кнезера имеет вершины. Каждая вершина имеет ровно соседей.${\displaystyle К(н,к)}$${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {nk}{k}}}$

Граф Кнезера является вершинно-транзитивным и дуго-транзитивным . Когда , граф Кнезера является сильно регулярным графом с параметрами . Однако он не является сильно регулярным, когда , так как разные пары несмежных вершин имеют разное количество общих соседей в зависимости от размера пересечения соответствующих пар множеств.${\displaystyle к=2}$${\displaystyle ({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3} 2}})}$${\displaystyle к>2}$

Поскольку графы Кнезера являются регулярными и транзитивными по ребрам , их связность вершин равна их степени , за исключением того, что является несвязным . Точнее, связность совпадает с числом соседей на вершину. ^[1]${\displaystyle К(2к,к)}$${\displaystyle К(н,к)}$${\displaystyle {\tbinom {nk}{k}},}$

Как предположил Кнезер (1956) , хроматическое число графа Кнезера для равно в точности n − 2 k + 2 ; например, граф Петерсена требует трех цветов в любой правильной раскраске . Эта гипотеза была доказана несколькими способами.${\displaystyle К(н,к)}$${\displaystyle n\geq 2k}$

• Ласло Ловас доказал это в 1978 году, используя топологические методы ^[2] , что дало начало области топологической комбинаторики .
• Вскоре после этого Имре Барани дал простое доказательство, используя теорему Борсука–Улама и лемму Дэвида Гейла . ^[3]
• Джошуа Э. Грин получил премию Моргана 2002 года за выдающиеся студенческие исследования за его еще более упрощенное, но все еще топологическое доказательство. ^[4]
• В 2004 году Иржи Матушек нашел чисто комбинаторное доказательство . ^[5]

Напротив, дробное хроматическое число этих графов равно . ^[6] Когда , не имеет ребер и его хроматическое число равно 1.${\displaystyle н/к}$${\displaystyle n<2k}$${\displaystyle К(н,к)}$

Хорошо известно, что граф Петерсена не является гамильтоновым , но долгое время предполагалось, что это единственное исключение и что любой другой связный граф Кнезера K ( n , k ) является гамильтоновым.

В 2003 году Чен показал, что граф Кнезера K ( n , k ) содержит гамильтонов цикл, если ^[7]

${\displaystyle n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).}$

С

${\displaystyle {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1}$

справедливо для всех , это условие выполняется, если${\displaystyle к}$

${\displaystyle n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\приблизительно 2,62k+1.}$

Примерно в то же время Шилдс показал (вычислительным путем), что, за исключением графа Петерсена, все связные графы Кнезера K ( n , k ) с n ≤ 27 являются гамильтоновыми. ^[8]

В 2021 году Мютце, Нумменпало и Вальчак доказали, что граф Кнезера K ( n , k ) содержит гамильтонов цикл, если существует неотрицательное целое число такое, что . ^[9] В частности, нечетный граф O _n имеет гамильтонов цикл, если n ≥ 4 . Наконец, в 2023 году Мерино, Мютце и Намрата завершили доказательство гипотезы. ^[10]${\displaystyle а}$${\displaystyle n=2k+2^{a}}$

Когда n < 3 k , граф Кнезера K ( n , k ) не содержит треугольников. В более общем случае, когда n < ck он не содержит клик размера c , тогда как он содержит такие клики, когда n ≥ ck . Более того, хотя граф Кнезера всегда содержит циклы длины четыре всякий раз, когда n ≥ 2 k + 2 , для значений n, близких к 2 k , кратчайший нечетный цикл может иметь переменную длину. ^[11]

Диаметр связного графа Кнезера K ( n , k ) равен ^[12 ]$${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.}$$

Спектр графа Кнезера K ( n , k ) состоит из k + 1 различных собственных значений : Причем происходит с кратностью для и имеет кратность 1. ^[13]$${\displaystyle \lambda _{j}=(-1)^{j}{\binom {nkj}{kj}},\qquad j=0,\ldots,k.}$$${\displaystyle \lambda _{j}}$ ${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$${\displaystyle j>0}$${\displaystyle \лямбда _{0}}$

Теорема Эрдеша –Ко–Радо утверждает, что число независимости графа Кнезера K ( n , k ) для равно${\displaystyle n\geq 2k}$$${\displaystyle \alpha (K(n,k))={\binom {n-1}{k-1}}.}$$

Граф Джонсона J ( n , k ) — это граф, вершины которого являются k -элементными подмножествами n -элементного множества, две вершины являются смежными, когда они встречаются в ( k  − 1) -элементном множестве. Граф Джонсона J ( n , 2) является дополнением графа Кнезера K ( n , 2) . Графы Джонсона тесно связаны со схемой Джонсона , обе из которых названы в честь Селмера М. Джонсона .

Обобщенный граф Кнезера K ( n , k , s ) имеет тот же набор вершин, что и граф Кнезера K ( n , k ) , но соединяет две вершины всякий раз, когда они соответствуют множествам, пересекающимся по s или меньшему количеству элементов. ^[11] Таким образом, K ( n , k , 0) = K ( n , k ) .

Двудольный граф Кнезера H ( n , k ) имеет в качестве вершин множества из k и n − k элементов, взятых из набора из n элементов. Две вершины соединены ребром, когда одно множество является подмножеством другого. Как и граф Кнезера, он вершинно транзитивен со степенью Двудольный граф Кнезера может быть образован как двудольное двойное покрытие K ( n , k ), в котором делается две копии каждой вершины и заменяется каждое ребро парой ребер, соединяющих соответствующие пары вершин. ^[14] Двудольный граф Кнезера H (5, 2) является графом Дезарга , а двудольный граф Кнезера H ( n , 1) является графом короны .${\displaystyle {\tbinom {n-k}{k}}.}$

• Вайсштейн, Эрик В. «График Кнезера». Математический мир .
• Вайсштейн, Эрик В. «Нечетный граф». MathWorld .