그래스만 그래프

그래스만 그래프
이름을 따서 명명됨	헤르만 그라스만
정점	${\displaystyle {\binom {n}{k}_{q}}}$
가장자리	${\displaystyle {\frac {q[k]_{q}[n-k]_{q}}}{2}}:{\binom {n}{k}}_{q}}}}}}$
지름	${\displaystyle \min(k,n-k)}$
특성.	거리-변환 연결된
표기법	${\displaystyle J_{q}(n,k)}$
그래프 및 모수 표

그래스만 그래프는 하위공간 시스템에서 정의한 단순한 그래프의 특별한 등급이다.Grassmann${\displaystyle {}_{}{그래프}_{}}$ ${\displaystyle \mathrm{Jq}}$(${\displaystyle n}$, k$$) {\$displaystyle J_{q}(n,$k)}의 정점은 $순서$ $q{\displaystyle }$ ${\displaystyle n}$ -차원 벡터 공간의 k ${\displaysty k}$ -dension$$ subspaces이며$,$ 두 정점은 교차점이 $({\displaystyle k}$- ${\displaystyle 1}$) ${\displaystyle)$일 때 인접한다.$k-1)}$ -차원$$.

Grassmann 그래프의 많은 파라미터는$$q {\$displaystyle$q} -analogs로 Johnson 그래프와 동일한 그래프 속성을 여러 개 가지고 있다.

그래프-이론적 특성

• ${\displaystyle {Jq}_{}}$(${\displaystyle n}$, ${\displaystyle k}$) ${\displaystyle J_{q}(n,k)}$은(는) ${\displaystyle {Jq}_{}}$(${\displaystyle n}$, ${\displaystyle n}$- ${\displaystyle k}$) ${\displaystyle J_{q}(n,n-k)}$에 대해 이형이다$.$
• 모든 $0{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle d}$ ${\displaystyle \le }$ ${\displaystyle \mathrm{직경}}$ (${\displaystyle {Jq}_{}}$ ${\displaystyle {}_{}n}$, k${\displaystyle }$)${\displaystyle }$) ${\displaystyle 0\leq$ d$\\leq \operatorname {diam}(J_{q}(n,k$$)})$에 대해 $거리{\displaystyle }$ d$${\$d에서 정점$ $쌍$의 교차점은 $({\displaystyle k}$- ${\displaystyle d}$) ${\d)}$ -d$$}이다$$.
• ${\displaystyle \omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}},}$ which is to say that the clique number of ${\displaystyle J_{q}(n,k)}$ is given by an expression in terms its least and greatest eigenvalues ${\disp$$레이스타일 \lambda _{\min }$과(와) ${\displaystyle {\lambda max}_{}}$ ${\$ $\}\}.$

자동형성군

Projective 선형 그룹 ${\displaystyle \mathrm{PGL}}$ ${\displaystyle (n,}$ ${\displaystyle k}$${\displaystyle }$)에 대한 ${\displaystyle \mathrm{Aut}{q}_{}(n,}$$k$ )${\displaystyle$ $\operatorname$${Aut}(J_{q}(n,k)})$의 거리 변환 하위 그룹이 $있다$

In fact, unless ${\displaystyle n=2k}$ or ${\displaystyle k\in \{1,n-1\}}$, ${\displaystyle \operatorname {Aut} (J_{q}(n,k))}$ ≅ ${\displaystyle \operatorname {PGL} (n,q)}$; otherwise ${\displaystyle \operatorname {Aut} (J_$${q}(n,k))}$ ≅ ${\displaystyle \operatorname {PGL} (n,q)\times C_{2}}$or ${\displaystyle \operatorname {Aut} (J_{q}(n,k))}$ ≅ ${\displaystyle \operatorname {Sym} ([n]_{q})}$ respectively.^[1]

교차로 배열

거리-변환성의 ${\displaystyle {결과}_{}\mathrm{Jq}}$ ${\displaystyle (n}$, k$$) {\$displaystyle J_{q}(n,$k)}도 거리-정규적이다.Letting ${\displaystyle d}$ denote its diameter, the intersection array of ${\displaystyle J_{q}(n,k)}$ is given by ${\displaystyle \left\{b_{0},\ldots ,b_{d-1};c_{1},\ldots c_{d}\right\}}$ where:

• ${\displaystyle {}_{}}$ :${\displaystyle j_{}}$ ${\displaystyle {}^{}}$ + ${\displaystyle 1^{}}$[ ${\displaystyle k}$- j ${\displaystyle {}_{}}$ ${\displaystyle q_{}}$[$n$- k${\displaystyle }$- ${\displaystyle j}$ ${\displaystyle {}_{}}$ q $[\$ -$$ ] ${\displaystyle q_{}}$ $[\displaystyle$b_{$j}}=q^{$$+$1}[$k-j$]_{q$$}[$n-k-j]_{q$
• ${\displaystyle c_{}}$ ${\displaystyle j_{}}$ ${\displaystyle :=}$(${\displaystyle }$[ ${\displaystyle j}$ ${\displaystyle {}_{}}$ ${\displaystyle {q\mathrm{}}^{}{}_{}{}^{}}$) 2 ${\$ 모든$$ < j d ${\displaystyle$ 0<$j\j\leq d}$.

스펙트럼

• ${\displaystyle {Jq}_{}}$(${\displaystyle n}$, ${\displaystyle k}$) ${\displaystyle J_{q}(n,k)}$의 특성 다항식은 다음과$$ 같다.

$displaystyle \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]

참고 항목

• 그라스만어
• 존슨 그래프

참조