블록 설계

조합론에서 블록 설계(block設計, )는 같은 크기의 일련의 부분 집합들이 주어져 있는 유한 집합이다. 이 경우, 이러한 부분 집합을 블록()이라고 하며, 블록 설계는 (예를 들어) “개의 원소들을 포함하는 블록의 수는 원소의 선택에 상관없이 개”와 같은 꼴의 조건을 만족시켜야 한다.

 정의 
 존슨 결합 도식 속의 블록 설계 
세 자연수 가 주어졌다고 하자. -블록 설계 는 다음과 같은 데이터로 주어진다.
 크기 의 유한 집합 . 그 원소를 점(點, )이라고 한다.
 의, 크기 의 부분 집합들의 족 . 그 원소를 블록()이라고 한다. (여기서 는 의 부분 집합들 가운데 크기가 인 것들로 구성된, 멱집합의 부분 집합이다.)
이는 다음 조건을 만족시켜야 한다.
 개의 서로 다른 점들이 주어졌을 때, 이 점들을 모두 포함하는 블록의 개수는 선택한 점들에 상관없는 값 이다. (0을 제외하는 것은 피셔 부등식 등을 따르지 않는 를 배제하기 위함이다.)

두 -블록 설계 , 가 주어졌다고 하자. 만약 이 둘 사이에 전단사 함수

가 존재하여

라면, 와 가 서로 동형이라고 한다.

인 -블록 설계는 -슈타이너 계(Steiner系, )라고 한다. 보통, 인 -블록 설계 는 로 표기된다.

 일반적 결합 도식 속의 블록 설계 
위 정의는 결합 도식의 개념을 통해 일반화된다.

구체적으로, 결합 도식 이 주어졌다고 하자. 그렇다면, 그 복소수 계수 보스-메스너 대수

는 반단순 대수이며, 따라서 그 최소 멱등원들의 집합

를 정의할 수 있다. 특히,

는 항상 최소 멱등원이다. (는 모든 성분이 1인  정사각 행렬이다.)

이제, 계수

들을 정의할 수 있다. 의 부분 집합(즉,  속의 블록 부호) 가 주어졌을 때, 내부 분포

및 쌍대 내부 분포

를 정의할 수 있다.

만약 어떤 부분 집합 가 주어졌을 때, 만약 의 부분 집합 가 다음 조건을 만족시킬 경우, -블록 설계()라고 한다.
임의의 에 대하여, 
만약 가 존슨 결합 대수일 때, 이는 첫째 정의로 귀결된다.

 연산 
 유도 블록 설계 
임의의 -블록 설계  및 점 가 주어졌다고 하자. 그렇다면,

는 -블록 설계를 이루며,

이다. 이를 의 유도 블록 설계(誘導block設計, )이라고 한다. (서로 다른 점에서 취한 유도 블록 설계는 서로 동형이지 못할 수 있다.)

특히, 슈타이너 계의 유도 블록 설계는 항상 슈타이너 계이다.

 결합 행렬 
-블록 설계 에서, 와  위에 각각 임의로 전순서를 주자. 그렇다면, 의 결합 행렬()은 다음과 같은  행렬

이다.

정사각 블록 설계의 경우 결합 행렬은 정사각 행렬이다.

 성질 
임의의 -블록 설계 가 주어졌을 때, 다음 정수들을 정의하자.

그렇다면, 다음이 성립한다.
 가 주어졌을 때, 개의 점들을 모두 포함하는 블록의 개수는 정확히 이다.

특히, 일 경우,
 블록의 수는 이다.

이에 따라, 모든 -블록 설계는 임의의 에 대하여 -블록 설계이다.

 존재의 필요 조건 
피셔 부등식(Fisher不等式, )에 따르면, 임의의 -블록 설계 에 대하여, 다음이 성립한다.

(이므로, 두 조건은 사실 동치이다.) 이 부등식을 포화시키는 블록 설계, 즉 점의 수가 블록의 수와 같은 2-블록 설계를 정사각 블록 설계(正四角block設計, ) 또는 대칭 블록 설계(對稱block設計, )라고 한다.

보다 일반적으로, 임의의 -블록 설계 에 대하여, 다음이 성립한다.

브룩-라이저-차울라 정리(Bruck-Ryser-चावला定理, )에 따르면, 임의의 -블록 설계 에 대하여, 만약 라면,
 만약 가 짝수라면, 는 제곱수이다.
 만약 가 홀수라면, 를 만족시키는 정수 가 존재한다.

 개수 
작은 크기의 -슈타이너 계의 동형류들의 수들은 다음과 같다. 
  1  3  7  9  13  15  19 … -슈타이너 계의 동형류의 수 1  1  1  1  2  80  11084874829

작은 크기의 -슈타이너 계의 동형류들의 수들은 다음과 같다. 
  1  2  4  8  10  14  16 … -슈타이너 계의 동형류의 수 1  1  1  1  1  4  1054163

 예 
다음과 같은 (2,4,8)-블록 설계를 생각하자.

그렇다면,
 총 8개의 점이 있다 ().
 모든 블록의 크기는 4이다 ().
 블록의 수는 14이다 ().
 임의의 한 점은 7개의 블록에 포함된다 ().
 임의의 두 점은 3개의 블록에 포함된다 ().

 파노 평면 
파노 평면 (유한체  위의 사영 평면) 을 생각하자.
300px
여기서, 각 선을 블록으로 생각하자. 즉, 다음과 같은 블록 설계를 생각하자.

이는 -슈타이너 계를 이룬다.
 총 7개의 점이 있다 ().
 모든 블록은 정확히 세 개의 점을 갖는다 ().
 블록의 수는 7이다 ().
 모든 점은 정확히 세 개의 블록에 포함된다 ().
 임의의 서로 다른 두 점이 주어졌을 때, 이를 포함하는 블록은 정확히 한 개이다. ().

 이진 골레 부호 

이진 골레 부호 는 759개의 옥타드(값이 1인 성분이 8개인 벡터)를 가지며, 각 옥타드를 의, 크기 8의 부분 집합으로 여길 수 있다. 이에 따라, 이진 골레 부호의 옥타드의 집합은 (5,8,24)-슈타이너 계를 이룬다. 이는 비트 설계(Witt設計, )라고 불린다.

 아다마르 설계 

 아다마르 행렬이 주어졌으며, 그 첫 열과 첫 행이 모두 1로 구성돼 있다고 하자. 그렇다면, 첫 열과 첫 행을 제거하고, 나머지 성분 가운데 −1을 0으로 치환한 뒤, 이를 어떤 정사각 블록 설계의 결합 행렬로 해석할 수 있다. 이를 아다마르 설계라고 하며, 이는 인 -블록 설계이다.

 자명한 블록 설계 
임의의 유한 집합  및 에 대하여, 는 인 -블록 설계를 이룬다.

임의의 유한 집합  및 양의 정수 에 대하여, 는 -블록 설계를 이루며, 이 경우

이다. 이는 이므로 정사각 블록 설계이며, 이므로 슈타이너 계이다.

 역사 
섬네일|오른쪽|웨슬리 스토커 바커 울하우스
섬네일|오른쪽|야코프 슈타이너
1844년에 영국의 보험계리인 웨슬리 스토커 바커 울하우스(, 1809~1893)가 자신이 편집자로 있던 잡지 《레이디즈 앤드 젠틀먼즈 다이어리》()에서 블록 설계에 대한 퍼즐을 제시하였다. 그 전문(全文)은 다음과 같다.

이는 현대적 용어로는 -슈타이너 계를 다루는 것이다.

이후 이 문제는 1847년에 영국의 잉글랜드 성공회 사제 토머스 페닝턴 커크먼(, 1806~1895)이 해결하였다. 그러나 이들의 논문은 크게 관심을 불러일으키지 못했다.

이후 울하우스와 커크먼과 독자적으로 야코프 슈타이너가 1853년에 블록 설계에 대한 논문을 출판하였다. 이후 그의 이름을 따 인 -블록 설계는 “슈타이너 계”로 불리게 되었다.

비트 설계는 1931년에 로버트 대니얼 카마이클이 최초로 발견하였으며, 에른스트 비트가 1938년에 마티외 군을 연구하던 도중 재발견하였다.

피셔 부등식은 로널드 피셔가 1940년에 증명하였다.

 참고 문헌 




 외부 링크 




















분류:조합론
분류:실험 설계
분류:집합족