Grassmannův graf - Grassmann graph

Grassmannův graf
Pojmenoval podle	Hermann Grassmann
Vrcholy
Hrany
Průměr
Vlastnosti	Přechodná vzdálenost ; Připojeno
Zápis
	Tabulka grafů a parametrů

Grassmannovy grafy jsou speciální třídou jednoduché grafy definované ze systémů podprostorů. Vrcholy Grassmannova grafu ${ displaystyle J_ {q} (n, k)}$ jsou ${ displaystyle k}$ -rozměrné podprostory an ${ displaystyle n}$ -dimenzionální vektorový prostor přes konečné pole řádu ${ displaystyle q}$ ; dva vrcholy sousedí, když je jejich průsečík ${ displaystyle (k-1)}$ -dimenzionální.

Mnoho parametrů Grassmannových grafů je ${ displaystyle q}$ -analogy parametrů Johnsonovy grafy a Grassmannovy grafy mají několik stejných vlastnosti grafu jako Johnsonovy grafy.

Graficko-teoretické vlastnosti

${ displaystyle J_ {q} (n, k)}$ je izomorfní s ${ displaystyle J_ {q} (n, n-k)}$ .
Pro všechny ${ displaystyle 0 leq d leq operatorname {diam} (J_ {q} (n, k))}$ , průnik libovolného páru vrcholů ve vzdálenosti ${ displaystyle d}$ je ${ displaystyle (k-d)}$ -dimenzionální.
${ displaystyle omega left (J_ {q} (n, k) right) = 1 - { frac { lambda _ { max}} { lambda _ { min}}},}$ což znamená, že číslo kliky z ${ displaystyle J_ {q} (n, k)}$ je dán výrazem ve smyslu jeho nejmenších a největších vlastních čísel ${ displaystyle lambda _ { min}}$ a ${ displaystyle lambda _ { max}}$ .

Automorfická skupina

Tady je vzdálenost-tranzitivní podskupina ${ displaystyle operatorname {Aut} (J_ {q} (n, k))}$ izomorfní k projektivní lineární skupině ${ displaystyle operatorname {PGL} (n, q)}$ .

Ve skutečnosti, pokud ${ displaystyle n = 2k}$ nebo ${ displaystyle k in {1, n-1 }}$ , ${ displaystyle operatorname {Aut} (J_ {q} (n, k))}$ $≅$ ${ displaystyle operatorname {PGL} (n, q)}$ ; v opačném případě ${ displaystyle operatorname {Aut} (J_ {q} (n, k))}$ $≅$ ${ displaystyle operatorname {PGL} (n, q) krát C_ {2}}$ nebo ${ displaystyle operatorname {Aut} (J_ {q} (n, k))}$ $≅$ ${ displaystyle operatorname {Sym} ([n] _ {q})}$ resp.^[1]

Křižovatkové pole

V důsledku toho, že jsme přechodní na vzdálenost, ${ displaystyle J_ {q} (n, k)}$ je také vzdálenost-pravidelná. Pronájem ${ displaystyle d}$ označit jeho průměr, průnik pole ${ displaystyle J_ {q} (n, k)}$ je dána ${ displaystyle left {b_ {0}, ldots, b_ {d-1}; c_ {1}, ldots c_ {d} right }}$ kde:

${ displaystyle b_ {j}: = q ^ {2j + 1} [k-j] _ {q} [n-k-j] _ {q}}$ pro všechny ${ displaystyle 0 leq j$ .
${ displaystyle c_ {j}: = ([j] _ {q}) ^ {2}}$ pro všechny ${ displaystyle 0$ .

Spektrum

Charakteristický polynom z ${ displaystyle J_ {q} (n, k)}$ je dána

{ displaystyle varphi (x): = prod limity _ {j = 0} ^ { operatorname {diam} (J_ {q} (n, k))} left (x- left (q ^ { j + 1} [kj] _ {q} [nkj] _ {q} - [j] _ {q} doprava) doprava) ^ { doleva ({ binom {n} {j}} _ {q } - { binom {n} {j-1}} _ {q} right)}}

.^[1]

Viz také

Reference

^ ^A ^b Brouwer, Andries E. (1989). Vzdálené pravidelné grafy. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.

[:0-1] A ^b Brouwer, Andries E. (1989). Vzdálené pravidelné grafy. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.

[1]