블록 설계

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

정의편집

존슨 결합 도식 속의 블록 설계편집

자연수  가 주어졌다고 하자.  -블록 설계  는 다음과 같은 데이터로 주어진다.

  • 크기  유한 집합  . 그 원소를 (點, 영어: point)이라고 한다.
  •  의, 크기  의 부분 집합들의 족  . 그 원소를 블록(영어: block)이라고 한다. (여기서   의 부분 집합들 가운데 크기가  인 것들로 구성된, 멱집합의 부분 집합이다.)

이는 다음 조건을 만족시켜야 한다.

  •  개의 서로 다른 점들이 주어졌을 때, 이 점들을 모두 포함하는 블록의 개수는 선택한 점들에 상관없는 값  이다. (0을 제외하는 것은 피셔 부등식 등을 따르지 않는  를 배제하기 위함이다.)

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

 

가 존재하여

 

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

  -블록 설계는  -슈타이너 계(Steiner系, 영어: Steiner system 스타이너 시스템[*])라고 한다. 보통,   -블록 설계   로 표기된다.

일반적 결합 도식 속의 블록 설계편집

위 정의는 결합 도식의 개념을 통해 일반화된다.[5][6]:2483–2486, §Ⅲ

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

 

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

 
 
 

를 정의할 수 있다. 특히,

 

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

이제, 계수

 

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

 

및 쌍대 내부 분포

 

를 정의할 수 있다.

만약 어떤 부분 집합  가 주어졌을 때, 만약  의 부분 집합  가 다음 조건을 만족시킬 경우,  -블록 설계(영어:  -block design)라고 한다.[6]:2484, Definition 7

임의의  에 대하여,  

만약  존슨 결합 대수일 때, 이는 첫째 정의로 귀결된다.

연산편집

유도 블록 설계편집

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

 
 

 -블록 설계를 이루며,

 

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

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

결합 행렬편집

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

 

이다.

 

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

성질편집

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

 

그렇다면, 다음이 성립한다.

  •  가 주어졌을 때,  개의 점들을 모두 포함하는 블록의 개수는 정확히  이다.

특히,  일 경우,

  • 블록의 수는  이다.

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

존재의 필요 조건편집

피셔 부등식(Fisher不等式, 영어: Fisher’s inequality)에 따르면,[7] 임의의  -블록 설계  에 대하여, 다음이 성립한다.

 
 

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

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

 

브룩-라이저-차울라 정리(Bruck-Ryser-चावला定理, 영어: Bruck–Ryser–Chowla theorem)에 따르면,[9][10] 임의의  -블록 설계  에 대하여, 만약  라면,

  • 만약  짝수라면,  제곱수이다.
  • 만약  홀수라면,  를 만족시키는 정수  가 존재한다.

개수편집

작은 크기의  -슈타이너 계의 동형류들의 수들은 다음과 같다. (OEIS의 수열 A30129)

  1 3 7 9 13 15 19
 -슈타이너 계의 동형류의 수 1 1 1 1 2 80 11084874829

작은 크기의  -슈타이너 계의 동형류들의 수들은 다음과 같다. (OEIS의 수열 A51390)

  1 2 4 8 10 14 16
 -슈타이너 계의 동형류의 수 1 1 1 1 1 4 1054163

편집

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

 
 

그렇다면,

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

파노 평면편집

파노 평면 (유한체   위의 사영 평면)  을 생각하자.

 

여기서, 각 선을 블록으로 생각하자. 즉, 다음과 같은 블록 설계를 생각하자.

 
 

이는  -슈타이너 계를 이룬다.

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

이진 골레 부호편집

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

아다마르 설계편집

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

자명한 블록 설계편집

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

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

 

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

역사편집

 
웨슬리 스토커 바커 울하우스
 
야코프 슈타이너

1844년에 영국의 보험계리인 웨슬리 스토커 바커 울하우스(영어: Wesley Stoker Barker Woolhouse, 1809~1893)가 자신이 편집자로 있던 잡지 《레이디즈 앤드 젠틀먼즈 다이어리》(영어: Lady’s and Gentleman’s Diary)에서 블록 설계에 대한 퍼즐을 제시하였다.[11] 그 전문(全文)은 다음과 같다.

XV. 상금 문제 (1733번). 편집부 출제.
 개의 기호들로 만들 수 있는, 각각  개의 기호를 갖는 조합들의 수를 계산하라. 다만, 임의의  개의 기호들의 조합은 두 개 이상에 속할 수 없다.
XV. Oʀ PRIZE QUEST. (1733) ; by the Editor.
Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them shall be repeated in any other.

 
[11]

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

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

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

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

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

참고 문헌편집

  1. Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). 《Design theory. Volume 1》. Encyclopedia of Mathematics and its Applications (영어) 69 2판. Cambridge University Press. doi:10.1017/CBO9780511549533. ISBN 978-0-521-44432-3. 
  2. Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). 《Design theory. Volume 2》. Encyclopedia of Mathematics and its Applications (영어) 78 2판. Cambridge University Press. doi:10.1017/CBO9781139507660. ISBN 978-0-521-77231-0. 
  3. Stinson, Douglas R. (2003). 《Combinatorial designs: constructions and analysis》 (영어). Springer-Verlag. doi:10.1007/b97564. ISBN 978-0-387-95487-5. 
  4. Raghavarao, Damaraju; Padgett, Lakshmi V. (2005년 10월). 《Block designs: analysis, combinatorics and applications》. Series on Applied Mathematics (영어) 17. World Scientific. doi:10.1142/5846. ISBN 978-981-256-360-6. 
  5. Zieschang, Paul-Hermann (2005). 《Theory of association schemes》. Springer Monographs in Mathematics (영어). Springer-Verlag. doi:10.1007/3-540-30593-9. ISBN 978-3-540-26136-0. ISSN 1439-7382. 
  6. Delsarte, Philippe; Levenshtein, Vladimir Iosifovich (1998년 10월). “Association schemes and coding theory”. 《Institute of Electrical and Electronics Engineers Transactions on Information Theory》 (영어) 44 (6): 2477–2504. doi:10.1109/18.720545. ISSN 0018-9448. 
  7. Fisher, Ronald A. (1940년 1월). “An examination of the different possible solutions of a problem in incomplete blocks”. 《Annals of Eugenics》 (영어) 10 (1): 52–75. doi:10.1111/j.1469-1809.1940.tb02237.x. 
  8. Ray-Chaudhuri, Dijen K.; Wilson, Richard M. (1975). “On t-designs”. 《Osaka Journal of Mathematics》 (영어) 12 (3): 737–744. MR 0592624. Zbl 0342.05018. 
  9. Bruck, Richard Hubert; Ryser, Herbert John (1949). “The nonexistence of certain finite projective planes”. 《Canadian Journal of Mathematics》 (영어) 1: 88–93. doi:10.4153/cjm-1949-009-2. ISSN 0008-414X. 
  10. Chowla, Sarvadaman; Ryser, Herbert John (1950). “Combinatorial problems”. 《Canadian Journal of Mathematics》 (영어) 2: 93–99. doi:10.4153/cjm-1950-009-8. ISSN 0008-414X. 
  11. The Editor (1844). “XV. Or PRIZE QUEST. (1733)”. 《Lady’s and Gentleman’s Diary》 (영어) 141: 84–84. 
  12. Kirkman, Thomas P. (1847). “On a problem in combinations”. 《The Cambridge and Dublin Mathematical Journal》 (영어) 2: 191–204. 
  13. Steiner, Jakob (1853). “11. Combinatorische Aufgabe”. 《Journal für die Reine und Angewandte Mathematik》 (독일어) 45: 181–182. doi:10.1515/crll.1853.45.181. ISSN 0075-4102. 
  14. Carmichael, Robert Daniel (1931). “Tactical configurations of rank two”. 《American Journal of Mathematics》 (영어) 53: 217–240. doi:10.2307/2370885. JSTOR 10.2307/2370885. 
  15. Witt, Ernst (1938). “Die 5-Fach transitiven Gruppen von Mathieu”. 《Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg》 (독일어) 12: 256–264. doi:10.1007/BF02948947. 
  • Street, Anne Penfold; Street, Deborah J. (1987). 《Combinatorics of experimental design》 (영어). Clarendon Press. ISBN 0-19-853256-3. 
  • Lindner, Charles C.; Rosa, Alexander (1978). “Steiner quadruple systems — a survey”. 《Discrete Mathematics》 (영어) 22 (2): 147-181. doi:10.1016/0012-365X(78)90122-X. 

외부 링크편집