존슨 결합 도식

1. 개요

존슨 결합 도식은 유한 집합과 자연수를 사용하여 정의되는 결합 도식의 한 유형이다. 이진 존슨 결합 도식 J₂(k, n)은 크기 n인 유한 집합 S의 크기 k인 부분 집합들의 집합족 X와 해밍 거리를 기반으로 하는 이항 관계를 통해 정의된다. q진 존슨 결합 도식 Jq(k, n)은 유한 집합 Σ와 해밍 무게를 사용하여 정의되며, Σ의 크기에 따라 e와 f 함수를 통해 이항 관계가 결정된다. 존슨 결합 도식은 대칭 결합 도식이며, 집합의 크기는 q진의 경우 (q-1)^k * (n choose k)이다. 이진 존슨 결합 도식의 이항 관계 수는 ⌊n/2⌋ + 1개이며, 해밍 거리를 통해 두 원소 간의 관계를 파악할 수 있다. 존슨 결합 도식의 고윳값은 에벌라인 다항식을 사용하여 계산되며, 미국의 수학자 셀머 마틴 존슨에 의해 처음 도입되었다.

2. 정의

존슨 결합 도식은 이진 존슨 결합 도식과 q진 존슨 결합 도식 두 가지로 정의된다.

2.1. 이진 존슨 결합 도식

다음이 주어졌다고 하자.

* 크기 $n$의 유한 집합 $S$
* 자연수 $k\backslash le\; n$

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

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

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

2.2. <math>q</math>진 존슨 결합 도식 (<math>q\ge3</math>)

다음과 같은 조건이 주어졌다고 하자.

* 유한 점을 가진 집합 $(\backslash Sigma,\backslash bullet)$ ($|\backslash Sigma|\backslash ge2$). 이에 따라, $\backslash bullet$에 대하여 해밍 무게를 정의할 수 있다.
* 두 양의 정수

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

:$e,f\backslash colon\; \backslash Sigma^n\backslash times\backslash Sigma^n\backslash to\backslash \{0,1,\backslash dotsc,n\backslash \}$
:$e\backslash colon\; (u,v)\backslash mapsto\; \backslash left|\backslash \{i\backslash in\backslash \{0,\backslash dotsc,n-1\backslash \}\backslash colon\; u\_i=v\_i\backslash ne\backslash bullet\backslash \}\backslash right|$
:$f\backslash colon\; (u,v)\backslash mapsto\; \backslash left|\backslash \{i\backslash in\backslash \{0,\backslash dotsc,n-1\backslash \}\backslash colon\; u\_i\backslash ne\backslash bullet\backslash ne\; v\_i\backslash \}\backslash right|$

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

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

:$\backslash operatorname\; W\_k(\backslash Sigma^n)\backslash subseteq\backslash Sigma^n$
=\left\{
u\in\Sigma^n\colon k=|\{i\in\{0,\dotsc,n-1\}\colon u_i\ne\bullet\}|
\right\}


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

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

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