График Кнезера

О графе окрестностей Кнезера унимодулярных решеток см. Решетка Нимейера .

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

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

Примеры

Граф Кнезера O ₄ = K (7, 3)

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

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

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

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

Свойства

Основные свойства

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

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

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

Хроматическое число

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

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

Напротив, дробное хроматическое число этих графов равно $n/k$. Когда $n<2k$, $K(n,k)$ не имеет ребер и его хроматическое число равно 1.

циклы

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

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

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

С

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

держится для всех $k$ это условие выполняется, если

$$n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.$$

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

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

Клики

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

Диаметр

Диаметр равен связного графа K ( n , k ) Кнезера

$$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.$$

Спектр

Спектр k графа Кнезера K ( n , + 1 ) состоит из k различных собственных значений :

$$\lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.$$

Более того $\lambda _{j}$ происходит с множественностью ${\tbinom {n}{j}}-{\tbinom {n}{j-1}}$ для $j>0$ и $\lambda _{0}$ имеет кратность 1.

Номер независимости

Теорема Эрдеша -Ко-Радо утверждает, что число независимости графа Кнезера K ( n , k ) для $n\geq 2k$ является

$$\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 или меньшему количеству элементов. Таким образом, K ( п , k , 0) = K ( п , k ) .

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

Ссылки

Цитируемые работы

• Барань, Имре (1978), «Краткое доказательство гипотезы Кнезера», Журнал комбинаторной теории , серия A, 25 (3): 325–326, doi : 10.1016/0097-3165(78)90023-7 , MR   0514626
• Чен, Я-Чен (2003), «Гамильтоновы графы Кнезера без треугольников», Журнал комбинаторной теории , серия B, 89 (1): 1–16, doi : 10.1016/S0095-8956(03)00040-6 , MR   1999733
• Денли, Тристан (1997), «Нечетный обхват обобщенного графа Кнезера», Европейский журнал комбинаторики , 18 (6): 607–611, doi : 10.1006/eujc.1996.0122 , MR   1468332
• Годсил, Кристофер ; Мигер, Карен (2015), Теоремы Эрдеша-Ко-Радо: алгебраические подходы , Кембриджские исследования по высшей математике, Cambridge University Press, стр. 43, ISBN  9781107128446

• Грин, Джошуа Э. (2002), «Новое краткое доказательство гипотезы Кнезера», American Mathematical Monthly , 109 (10): 918–920, doi : 10.2307/3072460 , JSTOR   3072460 , MR   1941810
• Кнезер, Мартин (1956), «Задание 360», Годовой отчет Ассоциации немецких математиков , 58 (2): 27
• Ловас, Ласло (1978), «Гипотеза Кнезера, хроматическое число и гомотопия», Журнал комбинаторной теории , серия A, 25 (3): 319–324, doi : 10.1016/0097-3165(78)90022-5 , hdl : 10338.dmlcz/126050 , MR   0514625
• Матушек, Иржи (2004), «Комбинаторное доказательство гипотезы Кнезера», Combinatorica , 24 (1): 163–170, doi : 10.1007/s00493-004-0011-1 , hdl : 20.500.11850/50671 , MR   2057690 , S2CID   42583803
• Мютце, Торстен; Нумменпало, Джерри; Вальчак, Бартош (2021) [STOC 2018], «Разреженные графы Кнезера являются гамильтоновыми», Журнал Лондонского математического общества , 103 (4), Нью-Йорк: 912–919, arXiv : 1711.01636 , doi : 10.1112/jlms.12406 , МР   3826304
• Мерино, Артуро; Мютце, Торстен; Намрата (2023), «Гамильтоновы графы Кнезера», Труды 55-го ежегодного симпозиума ACM по теории вычислений , стр. 963–970, arXiv : 2212.03918 , doi : 10.1145/3564246.3585137 , ISBN  978-1-4503-9913-5
• Шилдс, Ян Бомонт (2004), Эвристика цикла Гамильтона в жестких графах , доктор философии. диссертация, Университет штата Северная Каролина , заархивировано из оригинала 17 сентября 2006 г. , получено 1 октября 2006 г.
• Симпсон, Дж. Э. (1991), «Гамильтоновы двудольные графы», Труды двадцать второй Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 1991) , Congressus Numerantium , vol. 85, стр. 97–110, МР   1152123
• Валенсия-Пабон, Марио; Вера, Хуан-Карлос (2005), «О диаметре графов Кнезера», Discrete Mathematics , 305 (1–3): 383–385, doi : 10.1016/j.disc.2005.10.001 , MR   2186709
• Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Журнал комбинаторной теории , 8 : 23–29, doi : 10.1016/S0021-9800(70)80005-9 , MR   0266804

Внешние ссылки

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