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

Грассман граф
Грассман граф
Назван в честь	Герман Грассманн
Вершины
Края
Диаметр	мин( к , п – к )
Характеристики	Дистанционно-транзитивный ; Подключено
Обозначения	J q ( п , к )
	Таблица графиков и параметров

В теории графов графы Грассмана представляют собой особый класс простых графов, определяемых системами подпространств . Вершины , графа Грассмана $(Jq n q k) —$ это $k$ подпространства $n$ -мерного векторного пространства над конечным полем порядка $;$ - мерные две вершины являются смежными, если их ( пересечение $k - 1)$ -мерно.

Многие параметры графов Грассмана являются $q$ -аналогами параметров графов Джонсона , а графы Грассмана обладают некоторыми из тех же свойств графа, что и графы Джонсона.

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

$J q (n, k)$ изоморфен $J q (n, n - k)$ .
Для всех $0 \leq d \leq diam(J q (n, k))$ пересечение d любой пары вершин на расстоянии $является$ ( $k - d) -мерным$ .
Кликовое число J $q и (n, k)$ задается выражением через его наименьшее и наибольшее значения $λ min$ собственные $λ max$ :

\omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}}

^{[ нужна ссылка ]}

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

Существует дистанционно-транзитивная подгруппа $\operatorname {Aut} (J_{q}(n,k))$ изоморфна проективной линейной группе $\operatorname {P\Gamma L} (n,q)$ .

Фактически, если только $n=2k$ или $k\in \{1,n-1\}$ , $\operatorname {Aut} (J_{q}(n,k))$ $≅$ $\operatorname {P\Gamma L} (n,q)$ ; в противном случае $\operatorname {Aut} (J_{q}(n,k))$ $≅$ $\operatorname {P\Gamma L} (n,q)\times C_{2}$ или $\operatorname {Aut} (J_{q}(n,k))$ $≅$ $\operatorname {Sym} ([n]_{q})$ соответственно. ^[1]

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

Вследствие транзитивности расстояния, $J_{q}(n,k)$ также является дистанционно регулярным . Сдача в аренду $d$ обозначим его диаметр, массив пересечений $J_{q}(n,k)$ дается $\left\{b_{0},\ldots ,b_{d-1};c_{1},\ldots c_{d}\right\}$ где:

$b_{j}:=q^{2j+1}[k-j]_{q}[n-k-j]_{q}$ для всех $0\leq j<d$ .
$c_{j}:=([j]_{q})^{2}$ для всех $0<j\leq d$ .

Спектр

Характеристический полином $J_{q}(n,k)$ дается

\varphi (x):=\prod \limits _{j=0}^{\operatorname {diam} (J_{q}(n,k))}\left(x-\left(q^{j+1}[k-j]_{q}[n-k-j]_{q}-[j]_{q}\right)\right)^{\left({\binom {n}{j}}_{q}-{\binom {n}{j-1}}_{q}\right)}

. ^[1]

См. также

Ссылки

^ Jump up to: ^а ^б Брауэр, Андрис Э. (1989). Дистанционно-регулярные графы . Коэн, Арье М., Ноймайер, Арнольд. Берлин, Гейдельберг: Springer Berlin Heidelberg. ISBN 9783642743436 . OCLC 851840609 .

[:0-1] Jump up to: ^а ^б Брауэр, Андрис Э. (1989). Дистанционно-регулярные графы . Коэн, Арье М., Ноймайер, Арнольд. Берлин, Гейдельберг: Springer Berlin Heidelberg. ISBN 9783642743436 . OCLC 851840609 .

[1]