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

Граф, вершины которого соответствуют комбинациям набора из n элементов.

В теории графов граф Кнезера 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) , изображенный справа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Клики

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

Диаметр

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

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

Спектр

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

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

кратностью^[13] ${\displaystyle \lambda _{j}}$ ${\displaystyle {\tbinom {n}{j}}-{\tbinom {n}{j-1}}}$ ${\displaystyle j>0}$ ${\displaystyle \lambda _{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}}.}$

Рекомендации

Примечания

1. Уоткинс (1970).
2. Ловас (1978).
3. Барань (1978).
4. Грин (2002).
5. Матушек (2004).
6. Годсил и Мигер (2015).
7. Чен (2003).
8. Шилдс (2004).
9. Мютце, Нумменпало и Вальчак (2021).
10. Меринос, Мютце и Намрата (2023).
11. Денли (1997).
12. Валенсия-Пабон и Вера (2005).
13. «Архивная копия» (PDF) . www.math.caltech.edu . Архивировано из оригинала (PDF) 23 марта 2012 года . Проверено 9 августа 2022 г.{{cite web}}: CS1 maint: archived copy as title (link)
14. Симпсон (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), «Нечетный обхват обобщенного графа Кнезера», European Journal of Combinatorics , 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), «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
• Шилдс, Ян Бомонт (2004), Эвристика цикла Гамильтона в жестких графах, доктор философии. диссертация, Университет штата Северная Каролина , заархивировано из оригинала 17 сентября 2006 г. , получено 1 октября 2006 г.
• Симпсон, Дж. Э. (1991), «Гамильтоновы двудольные графы», Труды двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 1991) , Конгрессус Нумерантиум, том. 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

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

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