Граф Джонсона - Johnson graph - Wikipedia

Граф Джонсона
Граф Джонсона J(5,2)
Названный в честь	Селмер М. Джонсон
Вершины	${\displaystyle {\binom {n}{k}}}$
Края	${\displaystyle {\frac {1}{2}}k(n-k){\binom {n}{k}}}$
Диаметр	${\displaystyle \min(k,n-k)}$
Характеристики	${\displaystyle k(n-k)}$-обычный Вершинно-транзитивный Дистанционно-транзитивный Гамильтон-связанный
Обозначение	${\displaystyle J(n,k)}$
Таблица графиков и параметров

Графики Джонсона особый класс неориентированные графы определяется из систем множеств. Вершины графа Джонсона ${\displaystyle J(n,k)}$ являются ${\displaystyle k}$-элементные подмножества ${\displaystyle n}$-комплект элементов; две вершины смежны, если пересечение двух вершин (подмножеств) содержит ${\displaystyle (k-1)}$-элементы.^[1] И графы Джонсона, и тесно связанные с ними Схема Джонсона названы в честь Селмер М. Джонсон.

Особые случаи

• ${\displaystyle J(n,1)}$ это полный график K_п.
• ${\displaystyle J(4,2)}$ это октаэдрический граф.
• ${\displaystyle J(5,2)}$ это дополнительный граф из Граф Петерсена,^[1] следовательно линейный график из K₅. В общем, для всех ${\displaystyle n}$, граф Джонсона ${\displaystyle J(n,2)}$ является дополнением к Граф Кнезера ${\displaystyle K(n,2).}$

Теоретико-графические свойства

• ${\displaystyle J(n,k)}$ изоморфен ${\displaystyle J(n,n-k).}$

• Для всех ${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$, любая пара вершин на расстоянии ${\displaystyle j}$ Поделиться ${\displaystyle k-j}$ общие элементы.

• ${\displaystyle J(n,k)}$ является Гамильтон-связанный, что означает, что каждая пара вершин образует концы Гамильтонов путь в графике. В частности, это означает, что он имеет гамильтонов цикл.^[2]

• Также известно, что граф Джонсона ${\displaystyle J(n,k)~}$ является${\displaystyle ~k(n-k)}$-вершинно-связанные.^[3]

• ${\displaystyle J(n,k)}$ образует граф вершин и ребер (п - 1) -мерный многогранник, называется гиперсимплекс.^[4]

• то номер клики из ${\displaystyle J(n,k)}$ дается выражением через его наименьшее и наибольшее собственные значения: ${\displaystyle \omega (J(n,k))=1-{\tfrac {\lambda _{\max }}{\lambda _{\min }}}.}$

• В хроматическое число из ${\displaystyle J(n,k)}$ самое большее ${\displaystyle n,\chi (J(n,k))\leq n.}$^[5]

Группа автоморфизмов

Существует дистанционно-переходный подгруппа ${\displaystyle \operatorname {Aut} (J(n,k))}$ изоморфен ${\displaystyle \operatorname {Sym} (n)}$. Фактически, ${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$, пока не ${\displaystyle n=2k\geq 4}$; иначе, ${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}}$.^[6]

Массив пересечений

Как следствие того, что они дистанционно транзитивны, ${\displaystyle J(n,k)}$ это также дистанционно-регулярный. Сдача ${\displaystyle d}$ обозначим его диаметр, массив пересечений ${\displaystyle J(n,k)}$ дан кем-то

${\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}}$

куда:

${\displaystyle {\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}}$

Оказывается, если ${\displaystyle J(n,k)}$ является ${\displaystyle J(8,2)}$, его массив пересечений не используется совместно с каким-либо другим дистанционно регулярным графом; массив пересечений ${\displaystyle J(8,2)}$ разделяется с тремя другими дистанционно регулярными графами, которые не являются графами Джонсона.^[1]

Собственные значения и собственные векторы

• Характеристический многочлен ${\displaystyle J(n,k)}$ дан кем-то

${\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right)^{{\binom {n}{j}}-{\binom {n}{j-1}}}.}$

куда ${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.}$^[6]

• Собственные векторы ${\displaystyle J(n,k)}$ иметь четкое описание.^[7]

Схема Джонсона

Граф Джонсона ${\displaystyle J(n,k)}$ тесно связан с Схема Джонсона, схема ассоциации в котором каждая пара k-элементный набор связан с числом, половиной размера симметричная разница из двух наборов.^[8] Граф Джонсона имеет ребро для каждой пары множеств на расстоянии один в схеме ассоциации, и расстояния в схеме ассоциации в точности равны кратчайший путь расстояния в графе Джонсона.^[9]

Схема Джонсона также связана с другим семейством дистанционно-транзитивных графов, нечетные графики, вершины которого ${\displaystyle k}$-элементные подмножества ${\displaystyle (2k+1)}$-элементное множество, ребра которого соответствуют непересекающимся парам подмножеств.^[8]

Открытые проблемы

Свойства расширения вершин графов Джонсона, а также структура соответствующих экстремальных множеств вершин заданного размера до конца не изучены. Однако недавно была получена асимптотически точная нижняя оценка разложения больших множеств вершин.^[10]

В общем, определение хроматического числа графа Джонсона - открытая проблема.^[11]

Смотрите также

• Граф Грассмана

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

1. Холтон, Д. А .; Шихан, Дж. (1993), «Графики Джонсона и даже графики», Граф Петерсена, Серия лекций Австралийского математического общества, 7, Кембридж: Издательство Кембриджского университета, стр. 300, Дои:10.1017 / CBO9780511662058, ISBN  0-521-43594-3, МИСТЕР  1232658.
2. Альспах, Брайан (2013), «Графы Джонсона гамильтоновы связны», Ars Mathematica Contemporanea, 6 (1): 21–23, Дои:10.26493/1855-3974.291.574.
3. Ньюман, Илан; Рабинович, Юрий (2015), О связности фасетных графов симплициальных комплексов, arXiv:1502.02232, Bibcode:2015arXiv150202232N.
4. Рисполи, Фред Дж. (2008), График гиперсимплекса, arXiv:0811.2981, Bibcode:2008arXiv0811.2981R.
5. "Джонсон". www.win.tue.nl. Получено 2017-07-26.
6. Э., Брауэр, Андрис (1989). Дистанционно-регулярные графики. Коэн, Арджех М., Ноймайер, Арнольд. Берлин, Гейдельберг: Springer Berlin Heidelberg. ISBN  9783642743436. OCLC  851840609.
7. Фильмус, Юваль (2014), Ортогональный базис для функций над срезом булевого гиперкуба, arXiv:1406.0142, Bibcode:2014arXiv1406.0142F.
8. Кэмерон, Питер Дж. (1999), Группы перестановок, Студенческие тексты Лондонского математического общества, 45, Cambridge University Press, стр. 95, ISBN  9780521653787.
9. Таким образом, явное отождествление графов со схемами ассоциации можно увидеть в Боз, Р. К. (1963), "Сильно регулярные графы, частичные геометрии и частично сбалансированные планы", Тихоокеанский математический журнал, 13 (2): 389–419, Дои:10.2140 / pjm.1963.13.389, МИСТЕР  0157909.
10. Христофидес, Деметрес; Эллис, Дэвид; Кееваш, Питер (2013), "Приближенное вершинно-изопериметрическое неравенство для $ r $ -множеств", Электронный журнал комбинаторики, 4 (20).
11. 1949-, Годсил, К. Д. (Кристофер Дэвид) (2016). Теоремы Эрдеша-Ко-Радо: алгебраические подходы. Мигер, Карен (учитель колледжа). Кембридж, Соединенное Королевство. ISBN  9781107128446. OCLC  935456305.

внешняя ссылка

• Вайсштейн, Эрик В. «График Джонсона». MathWorld.
• Брауэр, Андрис Э. «Графики Джонсона».