존슨 결합 도식

조합론에서 존슨 결합 도식(Johnson結合圖式, 영어: Johnson scheme)은 주어진 해밍 무게의 벡터들로 구성된, 2진 해밍 결합 도식의 부분 결합 도식이다.

정의

이진 존슨 결합 도식

다음이 주어졌다고 하자.

• 크기 $n$의 유한 집합 $S$
• 자연수 $k\leq n$

그렇다면, 다음을 정의하자.

• $X=\operatorname {Pow} _{k}(S)$는 $S$의, 크기 $k$의 부분 집합들의 집합족이다.
• 각 $i\in \{0,1\dotsc ,n\}$ 및 $u,v\in X$에 대하여, 이항 관계 $u\sim _{i}v\iff \operatorname {d_{H}} (u,v)=2i$ (여기서 $\operatorname {d_{H}}$는 해밍 거리)

그렇다면, $(X,n,(\sim _{i})_{0\leq i\leq n})$는 결합 도식을 이루며, 이를 $(k,n)$-이진 존슨 결합 도식(영어: binary Johnson association scheme) $\operatorname {J} _{2}(k,n)$이라고 한다.

$q$진 존슨 결합 도식 ($q\geq 3$)

다음이 주어졌다고 하자.

• 유한 점을 가진 집합 $(\Sigma ,\bullet )$ ($|\Sigma |\geq 2$). 이에 따라, $\bullet$에 대하여 해밍 무게를 정의할 수 있다.
• 두 양의 정수 $0<k\leq n$

그렇다면, 다음과 같은 두 함수를 정의할 수 있다.

$e,f\colon \Sigma ^{n}\times \Sigma ^{n}\to \{0,1,\dotsc ,n\}$

$e\colon (u,v)\mapsto \left|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}=v_{i}\neq \bullet \}\right|$

$f\colon (u,v)\mapsto \left|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \neq v_{i}\}\right|$

(만약 $|\Sigma |\leq 2$라면, $e=f$이다.)

이제, $\bullet$에 대한 해밍 무게가 $k$인 길이 $n$의 $\Sigma$-문자열들의 집합

$\operatorname {W} _{k}(\Sigma ^{n})\subseteq \Sigma ^{n}=\left\{u\in \Sigma ^{n}\colon k=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \}|\right\}$

을 생각하자. 이 위에, 이항 관계

$u\sim _{i,j}v\iff \left(e(u,v),f(u,v)\right)=(k-i,k-j)\qquad (u,v\in \operatorname {W} _{k}(\Sigma ^{n}))$

를 정의하면, $(\operatorname {W} _{k}(\Sigma ^{n}),(\sim _{i,j})_{i,j})$는 결합 도식을 이룬다. 이를 $\Sigma$ 위의 존슨 결합 도식 $\operatorname {J} _{|\Sigma |}(k,n)$이라고 한다.

성질

$q$진 존슨 결합 도식 $\operatorname {J} _{q}(k,n)$은 대칭 결합 도식이며, 그 집합의 크기는 다음과 같다.

$|\operatorname {J} _{q}(k,n)|=(q-1)^{k}{\binom {n}{k}}$

이진 존슨 결합 도식 $\operatorname {J} _{2}(k,n)$의 이항 관계의 수는 (항등 관계를 포함하여) $\lfloor n/2\rfloor +1$개이며, 다음과 같다.

$\left\{\sim _{0,0},\;\sim _{1,1},\dotsc ,\sim _{\lfloor n/2\rfloor ,\lfloor n/2\rfloor }\right\}$

해밍 거리

존슨 결합 도식 $\operatorname {J} _{q}(k,n)$에서, 다음이 성립한다.^{:279, §1}

$u\sim _{i,j}v\implies \operatorname {d_{H}} (u,v)=i+j\qquad (u,v\in \operatorname {J} _{q}(k,n))$

증명:

임의의 $u,v\in \in \operatorname {J} _{q}(k,n)$에 대하여,

$e(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet \neq u_{i}=v_{i}\}|$

이므로,

$k-e(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet \neq u_{i}\neq v_{i}\}|$

이다. 마찬가지로,

$f(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \neq v_{i}\}|$

이므로,

$k-f(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet =u_{i}\neq v_{i}\}|$

이다. 즉,

$\operatorname {d_{H}} (u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq v_{i}\}|=(k-e(u,v))+(k-f(u,v))$

이다.

고윳값

이진 존슨 결합 도식 $\operatorname {J} _{2}(k,n)$의 고윳값들은 다음과 같다.

$p_{i,j}=e_{i}(j)$

$q_{i,j}={\frac {\mu _{i}}{v_{i}}}e_{i}(j)$

여기서

$\mu _{i}={\frac {n-2i+1}{n-i+1}}{\binom {n}{i}}$

$e_{i}(x)=\sum _{j=0}^{i}(-)^{j}{\binom {x}{j}}{\binom {k-x}{i-j}}{\binom {n-k-x}{i-j}}\qquad (i=0,\dotsc ,k)\in \mathbb {Z} [x]$

이며, 다항식열 $(e_{i})_{0\leq i\leq k}$를 에벌라인 다항식(Eberlein多項式, 영어: Eberlein polynomial)이라고 한다.

역사

미국의 수학자 셀머 마틴 존슨(영어: Selmer Martin Johnson, 1916~1996)이 도입하였다.

외부 링크

• “Association scheme”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Johnson scheme”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Eberlein polynomial”. 《Wolfram MathWorld》 (영어). Wolfram Research.