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

График Кнезера
График Кнезера
	Граф Кнезера K (5, 2) , ; изоморфен графу Петерсена
Назван в честь	Мартин Кнезер
Вершины
Края
Хроматическое число
Характеристики	-обычный ; дугопереходный
Обозначения	К ( п , к ), КГ п , к .
	Таблица графиков и параметров

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

Примеры

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

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

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

Граф Кнезера $O 4 = 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}},$ то же, что и число соседей на вершину. ^[1]

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

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

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

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

гамильтоновы циклы

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

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

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 \leq 27$ являются гамильтоновыми. ^[8]

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

Клики

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

Диаметр

Диаметр равен связного графа $K (n, k)$ Кнезера ^[12] $\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. ^[13]

Число независимости

Теорема Эрдеша -Ко-Радо утверждает, что число независимости графа Кнезера $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$ или меньшему количеству элементов. ^[11] Таким образом, $K (п, k, 0) = K (п, k)$ .

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

Ссылки

Примечания

^ Уоткинс (1970) .
^ Райдер (1978) .
^ Лэмб (1978) .
^ Грин (2002) .
^ Матоусек (2004) .
^ Годсил и Мигер (2015) .
^ Чен (2003) .
^ Шилдс (2004) .
^ Мютце, Нумменпало и Вальчак (2021) .
^ Меринос, Шапочка и Намрата (2023) .
^ Jump up to: ^а ^б Денли (1997) .
^ Валенсия-Пабон и Вера (2005) .
^ «Архивная копия» (PDF) . www.math.caltech.edu . Архивировано из оригинала (PDF) 23 марта 2012 года . Проверено 9 августа 2022 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ Симпсон (1991) .

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

Барань, Имре (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

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

[FOOTNOTEWatkins1970-1] Уоткинс (1970) .

[FOOTNOTELovász1978-2] Райдер (1978) .

[FOOTNOTEBárány1978-3] Лэмб (1978) .

[FOOTNOTEGreene2002-4] Грин (2002) .

[FOOTNOTEMatoušek2004-5] Матоусек (2004) .

[FOOTNOTEGodsilMeagher2015-6] Годсил и Мигер (2015) .

[FOOTNOTEChen2003-7] Чен (2003) .

[FOOTNOTEShields2004-8] Шилдс (2004) .

[FOOTNOTEMützeNummenpaloWalczak2021-9] Мютце, Нумменпало и Вальчак (2021) .

[FOOTNOTEMerinoMützeNamrata2023-10] Меринос, Шапочка и Намрата (2023) .

[FOOTNOTEDenley1997-11] Jump up to: ^а ^б Денли (1997) .

[FOOTNOTEValencia-PabonVera2005-12] Валенсия-Пабон и Вера (2005) .

[13] «Архивная копия» (PDF) . www.math.caltech.edu . Архивировано из оригинала (PDF) 23 марта 2012 года . Проверено 9 августа 2022 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[FOOTNOTESimpson1991-14] Симпсон (1991) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]