존슨 결합 도식

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

정의

이진 존슨 결합 도식

다음이 주어졌다고 하자.

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

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

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

그렇다면, $(X,n,({\sim }_i{)}_{0\le i\le n})$는 결합 도식을 이루며, 이를 $(k,n)$-이진 존슨 결합 도식(틀:Llang) ${\mathrm{J}}_2(k,n)$이라고 한다.

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

다음이 주어졌다고 하자.

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

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

$e,f:{\mathrm{\Sigma }}^n\times {\mathrm{\Sigma }}^n\to \{0,1,\dots ,n\}$

$e:(u,v)\mapsto |\{i\in \{0,\dots ,n-1\}:u_i=v_i\ne \bullet \}|$

$f:(u,v)\mapsto |\{i\in \{0,\dots ,n-1\}:u_i\ne \bullet \ne v_i\}|$

(만약 $|\mathrm{\Sigma }|\le 2$라면, $e=f$이다.)

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

${\mathrm{W}}_k({\mathrm{\Sigma }}^n)\subseteq {\mathrm{\Sigma }}^n=\{u\in {\mathrm{\Sigma }}^n:k=|\{i\in \{0,\dots ,n-1\}:u_i\ne \bullet \}|\}$

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

$u{\sim }_{i,j}v⟺(e(u,v),f(u,v))=(k-i,k-j)(u,v\in {\mathrm{W}}_k({\mathrm{\Sigma }}^n))$

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

성질

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

$|{\mathrm{J}}_q(k,n)|=(q-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})$

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

$\{{\sim }_{0,0},{\sim }_{1,1},\dots ,{\sim }_{\lfloor n/2\rfloor ,\lfloor n/2\rfloor }\}$

해밍 거리

존슨 결합 도식 ${\mathrm{J}}_q(k,n)$에서, 다음이 성립한다.틀:Rp

$u{\sim }_{i,j}v⟹{\mathrm{d}}_{\mathrm{H}}(u,v)=i+j(u,v\in {\mathrm{J}}_q(k,n))$

증명:

임의의 $u,v\in \in {\mathrm{J}}_q(k,n)$에 대하여,

$e(u,v)=|\{i\in \{0,\dots ,n-1\}:\bullet \ne u_i=v_i\}|$

이므로,

$k-e(u,v)=|\{i\in \{0,\dots ,n-1\}:\bullet \ne u_i\ne v_i\}|$

이다. 마찬가지로,

$f(u,v)=|\{i\in \{0,\dots ,n-1\}:u_i\ne \bullet \ne v_i\}|$

이므로,

$k-f(u,v)=|\{i\in \{0,\dots ,n-1\}:\bullet =u_i\ne v_i\}|$

이다. 즉,

${\mathrm{d}}_{\mathrm{H}}(u,v)=|\{i\in \{0,\dots ,n-1\}:u_i\ne v_i\}|=(k-e(u,v))+(k-f(u,v))$

이다.

고윳값

이진 존슨 결합 도식 ${\mathrm{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}(\genfrac{}{}{0ex}{}{n}{i})$

$e_i(x)=\sum _{j=0}^i(-{)}^j(\genfrac{}{}{0ex}{}{x}{j})(\genfrac{}{}{0ex}{}{k-x}{i-j})(\genfrac{}{}{0ex}{}{n-k-x}{i-j})(i=0,\dots ,k)\in \mathbb{Z}[x]$

이며, 다항식열 $(e_i{)}_{0\le i\le k}$를 에벌라인 다항식(Eberlein多項式, 틀:Llang)이라고 한다.

역사

미국의 수학자 셀머 마틴 존슨(틀:Llang, 1916~1996)이 도입하였다.

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:매스월드