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

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

В математике графы Джонсона — это особый класс неориентированных графов, определяемых из систем множеств. Вершины графа Джонсона — это -элементные подмножества -элементного множества; две вершины являются смежными, когда пересечение двух вершин (подмножеств) содержит -элементы. ^[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 ₅ . В более общем случае, для всех граф Джонсона является линейным графом K _n и дополнением графа Кнезера ${\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]
• Известно также, что граф Джонсона является -вершинно-связным. ^[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-\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. Холтон, DA; Шихан, Дж. (1993), "Графы Джонсона и даже графы", Граф Петерсена , Серия лекций Австралийского математического общества, т. 7, Кембридж: Издательство Кембриджского университета, стр. 300, doi : 10.1017/CBO9780511662058, ISBN 0-521-43594-3, г-н  1232658.
2. Alspach, Brian (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, MR  1072157; см. в частности стр. 89–90
7. Брауэр, Андрис Э. (1989), Дистанционно-регулярные графы , Коэн, Арье М., Ноймайер, Арнольд., Берлин, Гейдельберг: Springer Berlin Heidelberg, ISBN 9783642743436, OCLC  851840609
8. Filmus, Yuval (2014), "Ортогональный базис для функций над срезом булева гиперкуба", The Electronic Journal of Combinatorics , 23 , arXiv : 1406.0142 , Bibcode : 2014arXiv1406.0142F, doi : 10.37236/4567, S2CID  7416206.
9. Cameron, Peter J. (1999), Группы перестановок, London Mathematical Society Student Texts, т. 45, Cambridge University Press, стр. 95, ISBN 9780521653787.
10. Явную идентификацию графов со схемами ассоциации, таким образом, можно увидеть в Bose, RC (1963), "Строго регулярные графы, частичные геометрии и частично сбалансированные конструкции", Pacific Journal of Mathematics , 13 (2): 389–419, doi : 10.2140/pjm.1963.13.389 , MR  0157909.
11. Кристофидес, Деметрес; Эллис, Дэвид; Киваш, Питер (2013), «Приближенное вершинно-изопериметрическое неравенство для $r$-множеств», Электронный журнал комбинаторики , 4 (20).
12. Godsil, CD; Meagher, Karen (2016), Теоремы Эрдёша-Ко-Радо: алгебраические подходы , Кембридж, Соединенное Королевство, ISBN 9781107128446, OCLC  935456305{{citation}}: CS1 maint: location missing publisher (link)

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

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