Граф Кнезера

В теории графов граф Кнезера $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 3 = K (5, 2)$ является графом Петерсена (см. верхний правый рисунок).

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

Характеристики

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

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

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

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

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

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

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

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

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

Хорошо известно, что граф Петерсена не является гамильтоновым , но долгое время предполагалось, что это единственное исключение и что любой другой связный граф Кнезера $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

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

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

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

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

Клики

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

Диаметр

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

Спектр

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

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

Теорема Эрдеша –Ко–Радо утверждает, что число независимости графа Кнезера $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 (n, k, 0) = K (n, k)$ .

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

Ссылки

Примечания

^ Уоткинс (1970).
^ Ловас (1978).
^ Барани (1978).
^ Грин (2002).
^ Матоушек (2004).
^ Годсил и Мигер (2015).
^ Чэнь (2003).
^ Шилдс (2004).
^ Мютце, Нумменпало и Вальчак (2021).
^ Меринос, Мютце и Намрата (2023).
^ ab Denley (1997).
^ Валенсия-Пабон и Вера (2005).
^ "Архивная копия" (PDF) . www.math.caltech.edu . Архивировано из оригинала (PDF) 23 марта 2012 г. . Получено 9 августа 2022 г. .{{cite web}}: CS1 maint: archived copy as title (link)
^ Симпсон (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 Studies in Advanced Mathematics, Cambridge University Press, стр. 43, ISBN 9781107128446

Грин, Джошуа Э. (2002), «Новое короткое доказательство гипотезы Кнезера», American Mathematical Monthly , 109 (10): 918–920, doi :10.2307/3072460, JSTOR 3072460, MR 1941810
Кнезер, Мартин (1956), «Aufgabe 360», Jahresbericht der Deutschen Mathematiker-Vereinigung , 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), Эвристика цикла Гамильтона в жестких графах, докторская диссертация, Университет штата Северная Каролина , архивировано из оригинала 2006-09-17 , извлечено 2006-10-01
Симпсон, Дж. Э. (1991), «Гамильтоновы двудольные графы», Труды Двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 1991) , Congressus Numerantium, т. 85, стр. 97–110, MR 1152123
Валенсия-Пабон, Марио; Вера, Хуан-Карлос (2005), «О диаметре графов Кнезера», Дискретная математика , 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

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

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