График Джонсона

Класс неориентированных графов, определенных из систем множеств

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

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

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

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

• ${\displaystyle J(n,k)}$изоморфен ${\displaystyle J(n,n-k).}$
• Для all любая пара вершин, находящихся на расстоянии, имеет общие элементы. ${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$ ${\displaystyle j}$ ${\displaystyle k-j}$
• ${\displaystyle J(n,k)}$является гамильтоновым связным , что означает, что каждая пара вершин образует конечные точки гамильтонова пути в графе. В частности, это означает, что он имеет гамильтонов цикл. ^[2]
• Известно также, что граф Джонсона -вершинно связен . ^[3] ${\displaystyle J(n,k)~}$ ${\displaystyle ~k(n-k)}$
• ${\displaystyle J(n,k)}$образует граф вершин и ребер ( n  − 1)-мерного многогранника , называемый гиперсимплексом . ^[4]
• кликовое число определяется выражением через наименьшее и наибольшее собственные значения: ${\displaystyle J(n,k)}$ ${\displaystyle \omega (J(n,k))=1-{\tfrac {\lambda _{\max }}{\lambda _{\min }}}.}$
• Хроматическое число не более ^[5] ${\displaystyle J(n,k)}$ ${\displaystyle n,\chi (J(n,k))\leq n.}$
• Каждый граф Джонсона является локально сеточным, что означает, что индуцированный подграф соседей любой вершины является ладейным графом . Точнее, в графе Джонсона каждая окрестность является ладейным графом. ^[6] ${\displaystyle J(n,k)}$ ${\displaystyle k\times (n-k)}$

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

Существует дистанционно-транзитивная подгруппа , изоморфная . В действительности, за исключением того случая, когда , . ^[7] ${\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}}$

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

Вследствие того, что он дистанционно транзитивен, он также является дистанционно регулярным . Обозначив его диаметр, массив пересечений определяется выражением ${\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}}}$

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

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

• Характеристический полином имеет вид ${\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}}}.}$

где ^[7] ${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.}$

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

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

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

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

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

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

В целом определение хроматического числа графа Джонсона является открытой проблемой. ^[12]

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

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

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

1. Холтон, округ Колумбия; Шихан, Дж. (1993), «Графики Джонсона и даже графики», График Петерсена , Серия лекций Австралийского математического общества, том. 7, Кембридж: Издательство Кембриджского университета, стр. 7. 300, номер домена : 10.1017/CBO9780511662058, ISBN 0-521-43594-3, МР  1232658.
2. Альспах, Брайан (2013), «Графы Джонсона гамильтоново связны», Ars Mathematica Contemporanea , 6 (1): 21–23, doi : 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 , получено 26 июля 2017 г.
6. Коэн, Арье М. (1990), «Локальное распознавание графиков, зданий и связанных с ними геометрий» (PDF) , в Канторе, Уильям М.; Либлер, Роберт А.; Пейн, Стэнли Э.; Шульт, Эрнест Э. (ред.), Конечная геометрия, здания и смежные темы: материалы конференции по зданиям и связанным с ними геометриям, состоявшейся в Пингри-парке, штат Колорадо, 17–23 июля 1988 г. , Oxford Science Publications, Oxford University Press, С. 85–94, МР  1072157.; см., в частности, стр. 89–90.
7. Брауэр, Андрис Э. (1989), Дистанционно-регулярные графы , Коэн, Арье М., Ноймайер, Арнольд., Берлин, Гейдельберг: Springer Berlin Heidelberg, ISBN 9783642743436, OCLC  851840609
8. Филмус, Юваль (2014), «Ортогональный базис для функций над срезом булева гиперкуба», Электронный журнал комбинаторики , 23 , arXiv : 1406.0142 , Bibcode : 2014arXiv1406.0142F, doi : 10.37236/4567, S2CID  741620 6.
9. Кэмерон, Питер Дж. (1999), Группы перестановок, Студенческие тексты Лондонского математического общества, том. 45, Издательство Кембриджского университета, стр. 45. 95, ISBN 9780521653787.
10. Явную идентификацию графов с ассоциативными схемами таким образом можно увидеть в Bose, RC (1963), «Сильно регулярные графы, частичная геометрия и частично сбалансированные конструкции», Pacific Journal of Mathematics , 13 (2): 389– 419, номер документа : 10.2140/pjm.1963.13.389 , MR  0157909.
11. Христофидес, Деметрес; Эллис, Дэвид; Киваш, Питер (2013), «Приблизительное вершинно-изопериметрическое неравенство для $r$-множеств», Электронный журнал комбинаторики , 4 (20).
12. Годсил, компакт-диск; Мигер, Карен (2016), Теоремы Эрдеша-Ко-Радо: алгебраические подходы , Кембридж, Великобритания, ISBN 9781107128446, OCLC  935456305{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

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

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