대수적, 계통 발생론적 조합론의 몇 가지 주제들

Abstract

본 박사학위 논문은 크게 두 부분으로 나뉘어져 있는데 제 1 부에서는 completely regular code들에 관한 새로운 이론들에 대해서 다루고 있으며 제 2 부에서는 계통 발생론의 네트워크에 대한 내용들을 다루고 있다.제 1부를 요약하자면 다음과 같다.Completely regular code는 1973년에 Delsarte에 의해서 처음 소개 되었다. 모든 perfect code들은 completely regular code이기 때문에 completely regular code들의 집합은 perfect code들의 일반화된 집합으로 볼 수 있다. 1992년에 Neumaier가 equitable partition의 관점에서 completely regular code를 다르게 정의 하였는데 사실상 Delsarte가 정의한 것과 동치인 정의이다.제 1부에서는 각각의 Hamming graph들에서 completely regular code들의 카티션 곱(cartesian product)에 대해 소개하고 두 completely regular code의 카티션 곱(cartesian product)이 completely regular code가 되기 위한 필요 충분 조건을 찾았다. 또한 Hamming graph에서 등차 수열의 고유 값을 갖는 completely regular code들에 대해서 연구하였다. Leonard 정리를 이용하여 등차 수열의 고유 값을 갖는 completely regular partition에 의한 쿼션트 그래프(quotient graph)를 분류하였다. 이 결과를 이용하여 Hamming graph에서 등차 수열의 고유 값을 값는 선형 completely regular code들에 대해서는 모두 분류하였고, 이로써 커버링 반경이 1인 completely regular code들의 카티션 곱 (cartesian product)이 Hamming graph에서 등차 수열의 고유 값을 갖는 completely regular code들의 중요한 예임을 알 수 있다. 대수적 관점에서 이러한 특징을 Hamming graph가 아닌 일반적인 모든 거리 정칙 그래프에서 접근하기 위해 임의의 거리 정칙 그래프에서 $Q$-polynomial completely regular code를 정의하였다. 후에 completely regular code의 $Q$-polynomial의 조건이 특정한 Leonard pair의 존재성과 동치 조건임을 확인하였다. 이 결과를 이용하여 $Q$-polynomial completely regular code의 intersection number들이 부호(code)의 고유 값을 포함하여 6개의 파라미터들로 결정됨을 보였다. 마지막에는 Leonard completely code의 부분 집합인 harmonic completely regular code를 소개하였다.제 2 부를 요약하자면 다음과 같다. 계통 발생론는 분류학적 단위들의 집합들간의 진화적인 역사를 연구하는 학문이다. 계통 발생론적 분석은 주어진 생물학적 데이타를 가지고 생물학적 종들간에 관계를 트리(tree)로 나타내는게 목적이지만 교잡, 재조합, 수평적 유전자 이동 등에 의해 트리(tree)로 나타내는게 사실상 어렵다. 그렇기 때문에 트리(tree)가 아닌 좀 더 일반적인 그래프인 네트워크로 나타내고자 한다. 주어진 데이타를 가지고 네트워크로 나타내기 위한 방법으로써 1992년에 Bandelt와 Dress에 의해 split decomposition가 소개되었고 이 방법은 weakly compatible split system을 만들어 냈다. Weakly compatible split system을 만들기 위해 가장 많이 사용되는 방법으로는 split decomposition, NeighborNet, 그리고 QNet이다. Split decomposition과 NeighborNet은 거리에 기반을 둔 데이타를 가지고 네트워크를 생산하는 방법이며 QNet은 문자(character)에 기반을 둔 데이타를 가지고 네트워크를 생산하는 방법이다. 좀 더 자세히 얘기하자면, QNet은 quartet들의 데이타를 가지고 NegiborNet과 유사한 방법으로 네트워크를 생산한다. Split decomposition은 실제 데이타로부터 매우 적은 split들을 생산하는 반면에 NeighberNet과 QNet은 많은 split들을 생산할 수 있으며 두 방법(NeighborNet, QNet) 모두 circular split system을 만들어 낸다. 그러나 circular split system이 아닌 weakly compatible split system이 존재하기 때문에 보다 일반적인 방법이 필요하다. 그러므로 NeighborNet 또는 QNet을 발달 시키기 위해서 weakly compatible split system과 그것의 유도 quartet system에 대한 이해가 필요하다. 제 2부 에서는 weakly compatible split system에 의한 유도 quartet system의 크기 (quartet들의 개수) 에 대하여 연구하였다. 분류군의 집합 $X$ 의 크기가 7 이상일 때, 집합 $X$ 에 대한 split system이 maximal circular일 필요충분 조건이 split system에 의한 유도 quartet system의 크기가 $2 \binom{

X

}{4}$ 임을 보였다. 또한 거리 정칙 그래프와 이진법 코드를 이용하여, 분류군의 수가 무한대로 갈 때 4개의 분류군마다 유도 quartet들의 수가 0으로 수렴하는 maximal weakly compatible split system들을 만들어 냈다.

This thesis is divided into two parts. In part I, we study completely regular codes. More specifically, we study cartesian products of completely regular codes. This let to study of completely regular codes whose eigenvalues are in arithmetic progressions. This, in turn, let to the study of completely regular code from an algebraic viewpoint, namely we will introduce $Q$-polynomial codes which are a generalization of the above completely regular codes. In part II, we study weakly compatible split systems, which are a generalization of unrooted evolutionary trees, and commonly used to display reticulate evolution or ambiguity in biology data. We characterize all split systems which have exactly two quartets for each quadruple induced by some split. On the other hand, we construct maximal weakly compatible split systems where the number of induced quartets per quadruple tends to $0$ with the number of taxa going to infinity, using distance-regular graphs and binary completely regular codes.