존슨 결합 도식

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

정의

이진 존슨 결합 도식 
다음이 주어졌다고 하자.
 크기 의 유한 집합 
 자연수 
그렇다면, 다음을 정의하자.
 는 의, 크기 의 부분 집합들의 집합족이다.
 각  및 에 대하여, 이항 관계  (여기서 는 해밍 거리)
그렇다면, 는 결합 도식을 이루며, 이를 -이진 존슨 결합 도식() 이라고 한다.

진 존슨 결합 도식 () 
다음이 주어졌다고 하자.
 유한 점을 가진 집합  (). 이에 따라, 에 대하여 해밍 무게를 정의할 수 있다.
 두 양의 정수 
그렇다면, 다음과 같은 두 함수를 정의할 수 있다.

(만약 라면, 이다.)

이제, 에 대한 해밍 무게가 인 길이 의 -문자열들의 집합

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

를 정의하면, 는 결합 도식을 이룬다. 이를  위의 존슨 결합 도식 이라고 한다.

성질 
진 존슨 결합 도식 은 대칭 결합 도식이며, 그 집합의 크기는 다음과 같다.

이진 존슨 결합 도식 의 이항 관계의 수는 (항등 관계를 포함하여) 개이며,   다음과 같다.

해밍 거리 
존슨 결합 도식 에서, 다음이 성립한다.

증명:
임의의 에 대하여,

이므로,

이다. 마찬가지로,

이므로,

이다. 즉,

이다.

고윳값 
이진 존슨 결합 도식 의 고윳값들은 다음과 같다.

여기서

이며, 다항식열 를 에벌라인 다항식(Eberlein多項式, )이라고 한다.

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

참고 문헌

외부 링크 
 
 
 

조합론