Wykres Grassmanna

Wykres Grassmanna
Wykres Grassmanna
Nazwany po	Hermanna Grassmanna
Wierzchołki
Krawędzie
Średnica	min( k , n – k )
Nieruchomości	Połączone przechodnie na odległość ;
Notacja	J q ( n , k )
	Tabela wykresów i parametrów

W teorii grafów grafy Grassmanna są specjalną klasą grafów prostych zdefiniowanych na podstawie układów podprzestrzeni . Wierzchołki grafu Grassmanna $J q (n, k)$ są $k$ -wymiarowymi podprzestrzeniami $n$ -wymiarowej przestrzeni wektorowej nad skończonym ciałem rzędu $q$ ; dwa wierzchołki sąsiadują ze sobą, gdy ich przecięcie to $(k - 1)$ -wymiarowy.

Wiele parametrów wykresów Grassmanna jest $q$ -analogami parametrów wykresów Johnsona , a wykresy Grassmanna mają kilka takich samych właściwości wykresów jak wykresy Johnsona.

Własności teoretyczne grafów

$J q (n, k)$ jest izomorficzne z $J q (n, n - k)$ .
Dla wszystkich $0 \leq d \leq diam(J q (n, k))$ , przecięcie dowolnej pary wierzchołków w odległości $d$ jest $(k - d)$ -wymiarowe.
Liczba klik J $własnej q (n, k)$ jest wyrażona w postaci jej najmniejszej i największej wartości $λ min$ i $λ max$ :

{\ Displaystyle \ omega \ lewo (J_ {q} (n, k) \ prawej) = 1 - {\ Frac {\ lambda _ {\ max }}{\lambda _{\min }}}}

Grupa automorfizmów

Istnieje $_$ ${\ Displaystyle \ nazwa operatora {PGL} (n, q)}$ odległość podgrupa _ .

${\ Displaystyle \ nazwa operatora {Aut} (J_ {q} (n, k)}}$ rzeczywistości, chyba że $} {\ Displaystyle$ $\ in \ {1, n-1$ , $≅$ ${\ Displaystyle \ nazwa operatora {PGL} (n, q)}$ ; W przeciwnym razie ${\ Displaystyle \ nazwa operatora {Aut} (J_ {q} (n, k)}}$ $≅$ ${\ Displaystyle \ nazwa operatora {PGL} (n, q) \ razy C_ {2}}$ lub ${\ Displaystyle \ operatorname {Aut} (J_ {q} (n, k))}$ $≅$ ${\ Displaystyle \ nazwa operatora {Sym} ([n] _ {q})}$ odpowiednio.

Tablica przecięć

W konsekwencji bycia $przechodnim$ odległość również Pozwalając $oznaczenie$ $b$ tablica przez ${\ Displaystyle \ lewo \ {b_ {0}, \ ldots, b_ {d-1}; c_ {1}, \ ldots c_ {d} \ prawo \}} gdzie$ :

${\ Displaystyle b_ {j}: = q ^ {2j + 1} [kj] _ {q} [nkj] _ {q}}$ dla wszystkich ${\ Displaystyle 0 \ równoważnik j <d}$ .
${\ Displaystyle c_ {j}: = ([j] _ {q}) ^ {2}}$ dla wszystkich ${\ Displaystyle 0 <j \ równoważnik d}$ .

Widmo

przez Charakterystyczny $n$

{\ Displaystyle \ varphi (x): = \ prod \ ograniczenia _ {j = 0} ^ {\ nazwa operatora { średnica} (J_{q}(n,k))}\left(x-\left(q^{j+1}[kj]_{q}[nkj]_{q}-[j]_{q }\right)\right)^{\left({\binom {n}{j}}_{q}-{\binom {n}{j-1}}_{q}\right)}}

.

Zobacz też

^ ^a ^b Brouwer, Andries E. (1989). Wykresy odległości-regularne . Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436 . OCLC 851840609 .

[:0-1] Brouwer, Andries E. (1989). Wykresy odległości-regularne . Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436 . OCLC 851840609 .