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

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

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

Особые случаи [ править ]

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

Теоретико-графические свойства [ править ]

• ${\ Displaystyle J (п, к)}$ изоморфен ${\ displaystyle J (n, nk).}$

• В любом случае , любая пара вершин на расстоянии имеет общие элементы.${\ displaystyle 0 \ leq j \ leq \ operatorname {diam} (J (n, k))}$${\ displaystyle j}$${\ displaystyle kj}$

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

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

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

• кликой число из дается выражением в терминах его наименьшей и наибольшей собственных значений:${\ Displaystyle J (п, к)}$${\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 \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}}}.}$

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

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

Схема Джонсона [ править ]

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

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

Открытые проблемы [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. «График Джонсона» . MathWorld .
• Брауэр, Андрис Э. «Графы Джонсона» . CS1 maint: discouraged parameter (link)