조합론에서 존슨 결합 도식(Johnson結合圖式, 영어: Johnson scheme)은 주어진 해밍 무게의 벡터들로 구성된, 2진 해밍 결합 도식의 부분 결합 도식이다.
이진 존슨 결합 도식[편집]
다음이 주어졌다고 하자.
- 크기 의 유한 집합
- 자연수
그렇다면, 다음을 정의하자.
- 는 의, 크기 의 부분 집합들의 집합족이다.
- 각 및 에 대하여, 이항 관계 (여기서 는 해밍 거리)
그렇다면, 는 결합 도식을 이루며, 이를 -이진 존슨 결합 도식(영어: binary Johnson association scheme) 이라고 한다.
진 존슨 결합 도식 ()[편집]
다음이 주어졌다고 하자.
- 유한 점을 가진 집합 (). 이에 따라, 에 대하여 해밍 무게를 정의할 수 있다.
- 두 양의 정수
그렇다면, 다음과 같은 두 함수를 정의할 수 있다.
(만약 라면, 이다.)
이제, 에 대한 해밍 무게가 인 길이 의 -문자열들의 집합
을 생각하자. 이 위에, 이항 관계
를 정의하면, 는 결합 도식을 이룬다. 이를 위의 존슨 결합 도식 이라고 한다.[1]
진 존슨 결합 도식 은 대칭 결합 도식이며, 그 집합의 크기는 다음과 같다.
이진 존슨 결합 도식 의 이항 관계의 수는 (항등 관계를 포함하여) 개이며, 다음과 같다.
해밍 거리[편집]
존슨 결합 도식 에서, 다음이 성립한다.[1]:279, §1
증명:
임의의 에 대하여,
이므로,
이다. 마찬가지로,
이므로,
이다. 즉,
이다.
고윳값[편집]
이진 존슨 결합 도식 의 고윳값들은 다음과 같다.
여기서
이며, 다항식열 를 에벌라인 다항식(Eberlein多項式, 영어: Eberlein polynomial)이라고 한다.
미국의 수학자 셀머 마틴 존슨(영어: Selmer Martin Johnson, 1916~1996)이 도입하였다.
외부 링크[편집]