존슨 그래프

존슨 그래프
존슨 그래프 J(5,2)
이름을 따서 명명됨	셀머 존슨
정점	${\displaystyle {\binom {n}{k}}}$
가장자리	${\displaystyle {\frac {1}{2}}k(n-k){\binom {n}{k}}}}$
지름	${\displaystyle \min(k,n-k)}$
특성.	${\displaystyle k}$( ${\displaystyle n}$- ${\displaystyle k}$) ${\displaystyle k(n-k)}$ - 정규$$ 분포 정점 변환 거리-변환 해밀턴 연결
표기법	$(\displaystyle J(n,k)}$
그래프 및 모수 표

존슨 그래프는 집합의 시스템에서 정의된 특별 등급의 비방향 그래프다.존슨 그래프 J${\displaystyle (}n{\displaystyle }$, ${\displaystyle k}$) ${\displaystyle J(n,k)}$의 정점은 $n$ ${\displaystyle n}$ -element$$ set의 $k{\displaystyle }$ ${\displaystyle k}$ -element$$ set의 교차점이${\displaystyle }$( ${\displaystyle k}$- ${\displaystyle 1)}$ ${\displaystystyle (k-1)$-elements$$)를 포함할 때 두 정점이 인접한다.^[1]존슨 그래프와 밀접한 관련이 있는 존슨 방식은 모두 셀머 M. 존슨(Selmer M. Johnson)의 이름을 따서 명명되었다.

특례

• ${\displaystyle J(n}$, ${\displaystyle 1}$) ${\displaystyle J(n,1)}$이(가) 전체 그래프 K이다_n.
• ${\displaystyle J}$( ${\displaystyle 4}$,${\displaystyle 2}$) ${\displaystyle$J$(4,2)}$은 팔면 그래프다.
• ${\displaystyle J}$( ${\displaystyle 5}$,${\displaystyle 2}$) ${\displaystyle J (5,2)}$는 피터슨 그래프의 보완 그래프로서,^[1] 따라서 K의₅ 선 그래프인 것이다.보다 일반적으로 $모든{\displaystyle }$ n ${\displaystyle$ n$}$에$$대해 Johnson 그래프 $J{\displaystyle (n,}$ ${\displaystyle 2}$) ${\displaystyle$ J$(n,2$)는 Kneser 그래프 $K{\displaystyle (n,}$ ${\displaystyle 2}$)${\displaystyle }$. ${\displaysty K(n,2$)의 보완물이다$.$$}$

그래프-이론적 특성

• ${\displaystyle J}$( ${\displaystyle n}$, ${\displaystyle k}$) ${\displaystyle J(n,k)}$은(는$)$ $J{\displaystyle (,}$ n${\displaystyle }$- ${\displaystyle k}$)에 대해 이형이다${\displaystyle .}$ ${\displaystyle J(n,n-k$).$}$

• 모든 $0{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle j}$ ${\displaystyle \le }$ ${\displaystyle \mathrm{직경}}$ (${\displaystyle J}$(${\displaystyle n}$ ${\displaystyle ,}$ ${\displaystyle k}$)$}$ {\$displaystyle 0\leq$ j$\\leq \operatorname {diam}(J(n,k)})$에$$대해 거리 $j{\displaystyle }$ ${\$$displaysty$ $j}$에 있는 모든 정점 $쌍$은${\displaystyle }$k -$j$를 공유한다$.$

• ${\displaystyle J}$( ${\displaystyle n}$, k${\displaystyle }$) ${\displaystyle J(n,k)}$은 해밀턴으로 연결되며$$, 모든 정점 쌍이 그래프에서 해밀턴 경로의 끝점을 형성한다는 것을 의미한다.특히 해밀턴 사이클이 있다는 뜻이다.^[2]

• 존슨 그래프 $J{\displaystyle (n}$, k${\displaystyle }$) ${\$도 ${\displaystyle k}$(${\displaystyle n}$ -${\displaystyle }$k${\displaystyle }$)${\displaystyle ~k(n-k)}$ -vertex$$ 연결돼 있는 것으로 알려져$$ 있다.^[3]

• ${\displaystyle J(n}$, k${\displaystyle }$) ${\displaystyle J(n,k)}$는 하이퍼 복합체라고 하는 (n - 1)차원 폴리토프의 정점과 가장자리 그래프를 형성한다$$.^[4]

• the clique number of ${\displaystyle J(n,k)}$ is given by an expression in terms of its least and greatest eigenvalues: ${\displaystyle \omega (J(n,k))=1-{\tfrac {\lambda _{\max }}{\lambda _{\min }}}.$$}$

• $J{\displaystyle (n,}$ k${\displaystyle }$) ${\displaystyle J(n,$${\displaystyle k}$$)}$의 색수는 최대$$ $n{\displaystyle ,}$ ${\displaystyle \chi (J(}$n${\displaystyle ,}$ k${\displaystyle }$)${\displaystyle \le }$ ${\displaystyle n}$.${\displaystyle$ n$,\chi(J(n,k)\leq$ n$.}$이다.

자동형성군

There is a distance-transitive subgroup of ${\displaystyle \operatorname {Aut} (J(n,k))}$ isomorphic to ${\displaystyle \operatorname {Sym} (n)}$. In fact, ${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$, unless ${\di$$splaystyle n=2k\geq 4$ 그렇지 않으면 ${\displaystyle \mathrm{Auth}}$ ${\displaystyle }$(${\displaystyle J}$ ${\displaystyle (,k}$)${\displaystyle }$) ${\displaystyle \times }$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$^[6]

교차로 배열

거리 변환의 결과 $J{\displaystyle (n}$, ${\displaystyle k}$) ${\displaystyle J(n,k)}$도 거리 정규이다.$d{\displaystyle }$ ${\displaystyle d}$이(가) 직경을 나타내도록$$ 하면 $J{\displaystyle (n}$ ${\displaystyle ,}$ k${\displaystyle }$) ${\displaystyle J(n,k)}$의 교차 배열이 다음과 같이 지정된다$$.

${\displaystyle \left\{b_{0},\ldots,b_{d-1},c_{1},\ldots c_{d}\right\}}}}}$

여기서:

${\displaystyle {\required}b_{j}&=(k-j)(n-k-j)&#0\leq j<d\c_{j}&=j^{2}&0<j\leq d\end}정렬}}}}}}}}$

것으로 드러나지 않는 한 J(n, km그리고 4.9초 만){J(n,k)\displaystyle}은 J(8,2){J(8,2)\displaystyle}, 교차한 배열이 아니다 공유 다른 뚜렷한distance-regular 그래프, 교차 배열의 J(8,2){J(8,2)\displaystyle}공유된 3 다른distance-regular 그래프지 않는 존슨 그래프.[1]

고유값 및 고유 벡터

• $J{\displaystyle (n}$, ${\displaystyle k}$) ${\displaystyle J(n,k)}$의 특성 다항식은 다음에 의해 주어진다$$.

$[\displaystyle \phi(x):=\prod _{j=0}^{\operatorname {diam}(J(n,k))}\왼쪽(x-A_{n,k}(j)\right)^{{\binom{n}{j}-{\binom {n}{j-1}.}$

여기서 A ${\displaystyle n_{}}$, ${\displaystyle k_{}}$( ${\displaystyle j}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle k}$- ${\displaystyle j}$)${\displaystyle }$( n${\displaystyle }$- ${\displaystyle k}$- j${\displaystyle }$)${\displaystyle }$- j${\displaystyle }$. ${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.$$}$^[6]

• $J{\displaystyle (n}$, ${\displaystyle k}$) ${\displaystyle J(n,k)}$의 고유 벡터에는 명시적인 설명이 있다$$.^[7]

존슨 계획

존슨 그래프 $J{\displaystyle (n}$, ${\displaystyle k}$) ${\displaystyle J(n,k)}$은 각 k-element 집합 쌍이 두 집합의 대칭 차이의 절반 크기인 숫자와 연결된 연결 체계인 존슨 체계와 밀접하게 관련되어 있다$$.^[8]존슨 그래프는 연결 구성표에서 거리 1의 모든 세트 쌍에 대한 가장자리를 가지고 있으며, 연결 구성표에서의 거리는 존슨 그래프에서 정확히 가장 짧은 경로 거리다.^[9]

존슨 체계는 또한 거리 변환 그래프, 즉 홀수 그래프와 관련이 있는데, 이 그래프의 정점은 $({\displaystyle \mathrm{2k}}$+ ${\displaystyle 1}$) ${\displaystyle (2k+1)$-element$$ set의 $k{\displaystyle }$ ${\displaystyle k}$ -element$$ sets이고, 이 그래프의 가장자리는 부분 집합의 분리 쌍에 해당한다.^[8]

문제 열기

존슨 그래프의 꼭지점 확장 특성과 주어진 크기의 해당 극한 집합의 구조는 완전히 이해되지 않는다.그러나, 최근 정점의 큰 집합의 확장에 대해 점증적으로 꽉 조이는 하한선을 얻었다.^[10]

일반적으로 존슨 그래프의 색수를 결정하는 것은 개방적인 문제다.^[11]

참고 항목

• 그래스만 그래프

참조

외부 링크

• Weisstein, Eric W. "Johnson Graph". MathWorld.
• Brouwer, Andries E. "Johnson graphs".