존슨 결합 도식 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''존슨 결합 도식'''(Johnson結合圖式, {{llang|en|Johnson scheme}})은 주어진 [[해밍 무게]]의 벡터들로 구성된, 2진 [[해밍 결합 도식]]의 부분 결합 도식이다.

== 정의 ==
=== 이진 존슨 결합 도식 ===
다음이 주어졌다고 하자.
* 크기 <math>n</math>의 [[유한 집합]] <math>S</math>
* [[자연수]] <math>k\le n</math>
그렇다면, 다음을 정의하자.
* <math>X=\operatorname{Pow}_k(S)</math>는 <math>S</math>의, 크기 <math>k</math>의 [[부분 집합]]들의 [[집합족]]이다.
* 각 <math>i\in\{0,1\dotsc,n\}</math> 및 <math>u,v\in X</math>에 대하여, [[이항 관계]] <math>u\sim_iv\iff \operatorname{d_H}(u,v)=2i</math> (여기서 <math>\operatorname{d_H}</math>는 [[해밍 거리]])
그렇다면, <math>(X,n,(\sim_i)_{0\le i\le n})</math>는 [[결합 도식]]을 이루며, 이를 '''<math>(k,n)</math>-이진 존슨 결합 도식'''({{llang|en|binary Johnson association scheme}}) <math>\operatorname J_2(k,n)</math>이라고 한다.

=== <math>q</math>진 존슨 결합 도식 (<math>q\ge3</math>) ===
다음이 주어졌다고 하자.
* [[유한 집합|유한]] [[점을 가진 집합]] <math>(\Sigma,\bullet)</math> (<math>|\Sigma|\ge2</math>). 이에 따라, <math>\bullet</math>에 대하여 [[해밍 무게]]를 정의할 수 있다.
* 두 양의 정수 <math>0<k\le n</math>
그렇다면, 다음과 같은 두 함수를 정의할 수 있다.
:<math>e,f\colon \Sigma^n\times\Sigma^n\to\{0,1,\dotsc,n\}</math>
:<math>e\colon (u,v)\mapsto \left|\{i\in\{0,\dotsc,n-1\}\colon u_i=v_i\ne\bullet\}\right|</math>
:<math>f\colon (u,v)\mapsto \left|\{i\in\{0,\dotsc,n-1\}\colon u_i\ne\bullet\ne v_i\}\right|</math>
(만약 <math>|\Sigma|\le 2</math>라면, <math>e=f</math>이다.)

이제, <math>\bullet</math>에 대한 [[해밍 무게]]가 <math>k</math>인 길이 <math>n</math>의 <Math>\Sigma</math>-문자열들의 집합
:<math>\operatorname W_k(\Sigma^n)\subseteq\Sigma^n
=\left\{
u\in\Sigma^n\colon k=|\{i\in\{0,\dotsc,n-1\}\colon u_i\ne\bullet\}|
\right\}
</math>
을 생각하자. 이 위에, [[이항 관계]]
:<math>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))</math>
를 정의하면, <math>(\operatorname W_k(\Sigma^n),(\sim_{i,j})_{i,j})</math>는 [[결합 도식]]을 이룬다. 이를 <math>\Sigma</math> 위의 '''존슨 결합 도식''' <math>\operatorname J_{|\Sigma|}(k,n)</math>이라고 한다.<ref name="TAG">{{저널 인용|이름=Hannu|성=Tarnanen|이름2=Matti J.|성2=Aaltonen|이름3=Jean-Marie|성3=Goethals|제목=On the nonbinary Johnson scheme|doi=10.1016/S0195-6698(85)80039-1|저널=European Journal of Combinatorics|권=6|호=3|날짜=1985-09|쪽=279–285|zbl=0577.94014|언어=en}}</ref>

== 성질 ==
<math>q</math>진 존슨 결합 도식 <math>\operatorname J_q(k,n)</math>은 대칭 결합 도식이며, 그 [[집합의 크기]]는 다음과 같다.
:<math>|\operatorname J_q(k,n)|=(q-1)^k\binom nk</math>

이진 존슨 결합 도식 <math>\operatorname J_2(k,n)</math>의 [[이항 관계]]의 수는 (항등 관계를 포함하여) <math>\lfloor n/2\rfloor + 1</math>개이며,   다음과 같다.
:<math>\left\{\sim_{0,0},\;\sim_{1,1},\dotsc,\sim_{\lfloor n/2\rfloor,\lfloor n/2\rfloor}\right\}</math>

=== 해밍 거리 ===
존슨 결합 도식 <math>\operatorname J_q(k,n)</math>에서, 다음이 성립한다.<ref name="TAG"/>{{rp|279, §1}}
:<math>u\sim_{i,j}v \implies \operatorname{d_H}(u,v)=i+j\qquad(u,v\in\operatorname J_q(k,n))</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
임의의 <math>u,v\in\in\operatorname J_q(k,n)</math>에 대하여,
:<math>e(u,v)=|\{i\in\{0,\dotsc,n-1\}\colon \bullet\ne u_i = v_i\}|</math>
이므로,
:<math>k-e(u,v)=|\{i\in\{0,\dotsc,n-1\}\colon \bullet \ne u_i \ne v_i\}|</math>
이다. 마찬가지로,
:<math>f(u,v)=|\{i\in\{0,\dotsc,n-1\}\colon u_i \ne \bullet \ne v_i\}|</math>
이므로,
:<math>k-f(u,v)=|\{i\in\{0,\dotsc,n-1\}\colon \bullet = u_i \ne v_i \}|</math>
이다. 즉,
:<math>
\operatorname{d_H}(u,v)=
|\{i\in\{0,\dotsc,n-1\}\colon u_i \ne v_i \} |
= (k-e(u,v)) + (k-f(u,v))</math>
이다.
</div></div>

=== 고윳값 ===
이진 존슨 결합 도식 <math>\operatorname J_2(k,n)</math>의 고윳값들은 다음과 같다.
:<math>p_{i,j}=e_i(j)</math>
:<math>q_{i,j}=\frac{\mu_i}{v_i}e_i(j)</math>
여기서
:<math>\mu_i=\frac{n-2i+1}{n-i+1}\binom ni</math>
:<math>e_i(x)=\sum_{j=0}^i(-)^j{\binom xj}{\binom {k-x}{i-j}}{\binom {n-k-x}{i-j}}\qquad(i=0,\dotsc,k)
\in\mathbb Z[x]</math>
이며, 다항식열 <math>(e_i)_{0\le i\le k}</math>를 '''에벌라인 다항식'''(Eberlein多項式, {{llang|en|Eberlein polynomial}})이라고 한다.

== 역사 ==
미국의 수학자 셀머 마틴 존슨({{llang|en|Selmer Martin Johnson}}, 1916~1996)이 도입하였다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Association scheme}}
* {{매스월드|id=JohnsonScheme|title=Johnson scheme}}
* {{매스월드|id=EberleinPolynomial|title=Eberlein polynomial}}

[[분류:조합론]]