Граф Кнезера

редактировать

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

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

Содержание

1 Примеры
2 Свойства
3 Связанные графики
4 Ссылки
5 Внешние ссылки

Примеры

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

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

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

Свойства

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

Граф Кнезера транзитивен по вершинам и переходная дуга. Однако, как правило, это не строго регулярный граф, поскольку разные пары несмежных вершин имеют разное количество общих соседей в зависимости от размера пересечения соответствующей пары множеств.

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

Как предположил Кнезер (1955), хроматическое число графа Кнезера K (n, k) для $n ≥ 2 k {\ displaystyle n \ geq 2k}$ $n \ geq 2k$ равно n - 2k + 2; например, граф Петерсена требует трех цветов в любой правильной раскраске. Ласло Ловас (1978) доказал это с использованием топологических методов, что дало начало области топологической комбинаторики. Вскоре после этого Имре Барани (1978) дал простое доказательство, используя теорема Борсука – Улама и лемма Дэвида Гейла и Джошуа Э. Грин (2002) получили премию Моргана за еще более упрощенное, но все же топологическое доказательство. Иржи Матушек (2004) нашел чисто комбинаторное доказательство.

Граф Кнезера K (n, k) содержит гамильтониан цикл if (Чен 2003):

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

{\ displaystyle n \ geq {\ frac {1} {2}} \ left (3k + 1 + {\ sqrt {5k ^ {2} -2k + 1}} \ справа).}

Начиная с

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

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

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

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

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

Граф Кнезера K (n, k) содержит гамильтонов цикл, если существует неотрицательное целое число a такое, что $n = 2 k + 2 a {\ displaystyle n = 2k + 2 ^ {a}}$ ${\ displaystyle n = 2k + 2 ^ {a}}$ (Mütze, Nummenpalo Walczak 2018). В частности, нечетный граф Onимеет гамильтонов цикл, если n ≥ 4.

За исключением графа Петерсена, все связные графы Кнезера K (n, k) с n ≤ 27 являются гамильтоновыми (Shields 2004).

Когда n < 3k, the Kneser graph K(n, k) contains no triangles. More generally, when n < ck it does not contain клик размера c, тогда как он содержит такие клики, когда n ≥ ck. Более того, хотя граф Кнезера всегда содержит циклов длины четыре, когда n ≥ 2k + 2, для значений n, близких к 2k, самый короткий нечетный цикл может иметь непостоянную длину (Denley 1997).

диаметр связного графа Кнезера K (n, k) равен (Валенсия-Пабон и Вера 2005):

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

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

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

λ j = (- 1) j (n - k - jk - j), j = 0,…, k. {\ Displaystyle \ lambda _ {j} = (- 1) ^ {j} {\ binom {nkj} {kj}}, \ qquad j = 0, \ ldots, k.}

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

Кроме того,

λ j {\ displaystyle \ lambda _ {j}}

\ lambda _ {j}

встречается с multiplici ty

(nj) - (nj - 1) {\ displaystyle {\ tbinom {n} {j}} - {\ tbinom {n} {j-1}}}

{\ displaystyle {\ tbinom {n} {j}} - {\ tbinom {n} {j -1}}}

для

j>0 {\ displaystyle j>0}

j>0

λ 0 {\ displaystyle \ lambda _ {0}}

\ lambda _ {0}

имеет кратность 1. См. этот документ для подтверждения.

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

α (K (n, k)) = (n - 1 k - 1). {\ displaystyle \ alpha (K (n, k)) = {\ binom {n-1} {k-1}}.}

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

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

Ссылки

Bárány, Imre (1978), «Краткое доказательство гипотезы Кнезера», Journal of Combinatorial Theory, Series A, 25(3): 325–326, doi : 10.1016 / 0097- 3165 (78) 90023-7, MR 0514626
Чен, Я-Чен (2003), «Гамильтоновы графы Кнезера без треугольников», Journal of Combinatorial Theory, Series 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
Грин, Джошуа Э. (2002), «Новое краткое доказательство гипотезы Кнезера», American Mathematical Monthly, 109 (10): 918–920, doi : 10.2307 / 3072460, JSTOR 3072460, MR 1941810
Кнезер, Мартин (1955), «Aufgabe 360», Jahresberic ht der Deutschen Mathematiker-Vereinigung, 58(2): 27
Ловас, Ласло (1978), «Гипотеза Кнезера, хроматическое число и гомотопия», Journal of Combinatorial Theory, Series 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
Мютце, Торстен ; Нумменпало, Джерри; Вальчак, Бартош (2018), «Разреженные графы Кнезера являются гамильтоновыми», STOC'18 - Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений, Нью-Йорк: ACM, стр. 912–919, arXiv : 1711.01636, MR 3826304
Шилдс, Ян Бомонт (2004), Цикл Эвристики Гамильтона в жестких графах, доктор философии. дипломная работа, Государственный университет Северной Каролины, заархивировано из оригинала 17 сентября 2006 г., извлечено 01 октября 2006 г.
Simpson, JE (1991), "Гамильтоновы двудольные графы ", Труды Двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Лос-Анджелес, 1991), 85, стр. 97–110, MR 1152123
Валенсия- Пабон, Марио; Вера, Хуан-Карлос (2005), «О диаметре графов Кнезера», Дискретная математика, 305 (1–3): 383–385, doi : 10.1016 / j.disc.2005.10.001, MR 2186709
Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Journal of Combinatorial Theory, 8: 23– 29, doi : 10.1016 / S0021-9800 (70) 80005-9, MR 0266804

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