아무도 안 읽을걸 알지만 일단 시작을 하고 보자.

이 책의 제목인 Distance Regular Graph(DRG)에 대해서 먼저 설명을 할게.

이 책에서도 1.1 시작하기 전에 소개를 하네. 정의는 대충 써보면


정의. 그래프 G는 다음과 같은 정수들 b_i, c_i가 존재할 때 distance-regular라고 부른다:

거리가 i인 임의의 두 꼭지점 x, y에 대해서

(1) x와의 거리가 i-1이고 y와의 거리가 1인 꼭지점의 갯수는 c_i개이다.

(2) x와의 거리가 i+1이고 y와의 거리가 1인 꼭지점의 갯수는 b_i개이다.


그리고 d가 G의 diameter(=두 꼭지점 사이의 최대거리)일 때,

{b_0, b_1, ..., b_d-1;c_1, c_2, ..., c_d}를 G의 intersection array라고 한다.

얘를 보통 distance diagram이라는 아래와 같은 그림으로 표현해.



viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee87fa11d02831d3049d5484b72b456f01af270dee20f9ecc4e7e6bf5f63272339174ce8986f470540fe0485e3e1b29369d1


여기서 k = b_0는 valency라고 하고, G의 모든 꼭지점은 k개의 이웃을 가짐.

a_i = k - b_i - c_i로 정의하고, b_d = c_0 = 0, c_1 = 1로 정의됨.

Γ_i(x)는 기준이 되는 꼭지점인 x와 거리가 i인 꼭지점들의 모임이고 이 집합의 크기를 k_i라고 함, 특별히 Γ_1(x) = Γ(x)이고 k_1 = k.


이렇게 말해도 이해가 안 갈테니까 그림으로 정육면체가 왜 DRG인지를 알아보자.



viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee87fa11d02831d3049d5484b72b456f01af270dee20f9ecc4e7e6fb0f334e223d1d48e89f08475b12b49cc57d4a5f347d19b23526b0


정육면체에서 한 꼭지점 x를 잡은 다음에 거리를 이용해서 분류한게 처음 그림이야.

그걸 이용해서 distance diagram을 그린게 다음 그림이고, 이 그림에 intersection array (a_i, b_i, c_i)를 다 적어둠.


책에서 적어놓은 distance regular graph의 예는 다음과 같아.

다각형 : {2,1,...,1;1,...,1,c_d} (2d-gon일 때 c_d=2, (2d+1)-gon일 때 c_d=1)

정사면체 : {3;1}

정육면체 : {3,2,1;1,2,3}

정팔면체 : {4,1;1,4}

정이십면체 : {5,2,1;1,2,5}

정십이면체 : {3,2,1,1,1;1,1,1,2,3}

The Petersen graph : {3,2;1,1}

The line graph of the Petersen graph : {4,2,1;1,1,4}


이외에도 많긴 함. 특정한 intersection array를 가지는 애들을 classical parameter라고 하는데 얘는 6,9챕터에 나온다.


DRG는 대수적 그래프론에서 성질이 제일 좋은 놈들에 속해. 대충 대칭적으로 생겼고 그래프 고유치도 쉽게 구해지거든.

그러면 대충 다음과 같은 질문이 나오게 된다.


Q. DRG가 있으면 intersection array가 나오는데, 반대로 임의의 sequence로 DRG를 만들 수 있는가?

A. 당연히 대답은 No다. intersection array는 당연하겠지만 수많은 조건들을 다 만족시켜야 함.

하나만 얘기하자면 위의 예에서 볼 수 있듯이 b_i는 감소수열이고 c_i는 증가수열임. 그 외에도 졸라 많음.

이 책의 5챕터가 intersection array에 대한 조건들을 다룸. 근데 조건 다 만족시켜도 DRG가 존재하는지는 모름.


Q. 이런걸 왜 공부하냐?

A. 그러게 말이다. (한숨) 농담이고, 내가 최근에 계속 울궈먹는 이론이 DRG에 잘 먹혀서 공부 중.

예전에 아주 대충 공부했는데 이제는 정말 제대로 알아야겠더라.


Q. DRG는 classification이 되어있나?

A. 이게 분류가 굉장히 어렵다. D=2인 경우만 해도 Strongly regular graph라고 해서 따로 다룬다.

k가 고정되었을 때 DRG가 유한하다는건 밝혀졌긴 한데, 이게 밝혀진다고 다 구할 수 있는건 아니라서..

뭐 Type을 이래저래 나누거나 어떤 그래프를 포함하거나 포함하지 않거나 등등 다 나름대로의 기준을 정해서 분류를 한다.


질문하면 답변하려고 노력해볼게.

한글 섞어쓰니까 되게 쓰기 힘들다는건 알겠네.. 때려치지 않으면 다음 글에는 1.1부터 요약해서 써볼거임.