Ramsey Number 에 대해

(문제) R명의 사람이 있다. 사람들 사이에는 서로 친구이거나 서로 적인 관계가 성립하고 있다. 그렇다면 만약 R명의 사람이 존재하기만 한다면 이중에서 3명은 서로 친구이거나 3명이 서로 적인 경우가 반드시 존재한다고 한다. 이 경우 R의 최소 값은 얼마이겠는가?

위와 같은 문제가 주어졌다. 위 문제는 Ramsey Number를 제기하는 가장 기초적인 문제로써 비둘기 집의 원리로써 쉽게 해결 할 수 있다. 한편 여기서 3명이 서로 친구(mutual friends)란 말은 (대칭적으로 서로 적이란 말에도 성립한다.) 이 3명중에서 아무나 두 명을 선택했을 때 그 두 사람은 반드시 친구인 경우인 경우를 말한다.

(풀이)

사람이 총 n명이 있다고 가정하자. 그리고 각 사람들을 점(point)으로 두고 그 사람사이의 관계를 선(edge)으로 연결하자. 이 n 개의 점을 모두 다 이은 모양의 그래프(Graph)를 Complete graph of order n (K_n)이라고 한다. 이제 이 그래프의 선분들은 2가지색으로 Coloring을 할 수 있고, 그 색들은 각각, 친구, 적이라는 의미를 가진다고 생각하면 위 문제는 변의 색이 모두 같은 삼각형을 찾는 문제로 변형이 된다.

먼저 R>5 임을 보이자. 이것은 반례를 보이면 쉽게 증명된다.

① R=5 ; Counter Example.

② R=6 : 한 사람(A)에 대해서 생각하자. Pigeonhall Principle 에 의해서 나머지 다섯 사람 중에는 적어도 세 사람 이상이 A와 친구이거나 적이고, 대칭적으로 세 사람이 친구라고 한다면 이 사람들끼리 친구 사이가 존재하면 그 두 사람과 A는 서로 친구 사이. 만일 이 세 사람이 모두 적이라면 서로 적인 경우가 되므로 적어도 R이 6이상 이라면 반드시 세 명이 서로 친구이거나 서로 적인 경우가 존재한다. 따라서 R의 최소 값은 6이다. □

(Definition) R명의 사람이 있을 때 m명이 서로 친구이거나 (mutual friends), n명이 서로 적인 경우(mutual enemies)인 경우가 반드시 생긴다고 할 때, R의 최소값을 Ramsey Number R(m,n) 이라고 정의한다.

일반적으로 Ramsey Number 의 구체적인 값에 대해서는 알려져 있지 않다. 대신에 몇몇 특수한 값들에 대해서는 이미 밝혀지고 증명이 되어 있다. 필자는 이번 원고에서 R(4,4)=18 임을 증명하려 한다.

Lemma 1) R(3,3) = 6

위에 증명되어 있다.

Lemma 2) R(4,3) = 9

(풀이)

먼저 R(4,3) > 8 임을 보이자. 이것은 R=8 일 때 4명이 서로 친구이거나 3명이 서로 적일 경우가 꼭 생기지 않는 반례를 보이면 증명이 된다. 왜냐하면 R=8 일 때 반례가 존재하면 R<8 일 때 역시 R=8 일 때의 예에서 사람을 한 명씩만 줄이면 그것이 각각의 반례가 되기 때문이다. 친구를 실선, 적을 점선으로 연결한다고 하면 R=8 일 때 다음과 같은 반례가 존재한다.

이제 R(4,3)<= 9 임을 보이자.

어떤 한 사람 A를 기준으로 친구가 6명 있다고 가정하자. 그러면 Lemma 1에 의해 이 6명 중에는 반드시 서로 친구인 세 사람이 있거나 적인 세 사람이 존재한다. 서로 적인 세 사람이 존재한다면 R(4,3)의 정의에 만족하고, 서로 친구인 세 사람이 존재한다면 A와 함께 서로 친구인 네 사람이 존재하는 것이 된다. 따라서 증명 끝.

또한 A와 적관계인 4 사람이 존재한다고 가정하자. 그러면 이 사람들 중에 서로 적인 두 사람이 있다면 A와 함께 서로 적인 세 사람이 존재하는 것이다. 그런 관계가 없다면 정의에 의해 이 네 사람은 서로 친구가 되는 것이다. 따라서 9명의 사람이 있을 때, 어떤 한 사람도 친구가 6명 이상이거나 적이 4명 이상이면 반드시 네 명이 서로 친구이거나 세 명이 서로 적인 경우가 반드시 생기게 된다.

9가 R(4,3)을 만족하지 않을 반례가 존재하기 위해선 9명의 사람 모두가 5명의 친구, 3명의 적을 가지고 있어야 한다. 즉, 위와 같은 그래프에서 각 점에 실선이 모두 5개여야 한다는 말이다. 점과 실선(edge)만으로 이루어진 Simple Graph 를 생각하면,

2e = Σdeg(v) (e는 edge 의 개수, deg(v) 는 각 꼭지점에 연결된 edge의 개수)

가 성립하는 데, deg(v)=5 이고 |v|=9 이므로, 2e = Σdeg(v) = 9×5 = 45 이다.

하지만 45는 홀수 이므로 모순. 따라서 그러한 예는 존재하지 않는다. 따라서 반드시 누군가 한 명은 6명 이상의 친구를 가지고 있거나 4명 이상의 적을 가지고 있어야 한다. 따라서 9명의 사람이 있으면 반드시 네 명이 서로 친구이거나 세 명이 서로 적인 경우를 찾을 수 있고 R(4,3)>8 에서, R(4,3)=9 이다.□

Lemma 3)

R(m,n) = R(n,m)

Lemma 4)

R(n,2) = n = R(2,n)

(증명) Lemma 3와 Lemma 4는 자명하다.

Theorem) Ramsey's Theorem.

Claim. R(m,n) ≤ R(m-1,n) + R(m,n-1) for m, n(>2) ∈ N

pf) n명의 사람이 있다고 하자. 그 중에서 임의의 고정된 한 사람 A를 잡고 각 사람들 사이의 관계를 선으로 표시하자. 즉, 친구일 때는 붉은 색을, 적일 때는 푸른색의 선분을 칠한다고 생각하자. 만일 붉은 색이 선분이 R(m-1,n) 개 이상 있다고 하면 그 사람들이랑 A 와 함께 존재해서 R(m,n) 이 만들어진다. 비슷하게 푸른색이 R(m,n-1) 개 이상 있다고 하면 역시나 A와 함께 R(m,n) 이 만들어진다. 따라서 어떤 고정된 사람 A에 대하여 총 (R(m-1,n)-1)+(R(m,n-1)-1)+1 개의 관계를 가진 사람들이 존재하면 그 Pigeonhall Principle에 의해서 R(m-1,n) 개의 붉은 색 선분이나 R(m,n-1) 개의 푸른색 선분을 가진 사람들이 존재하고 따라서 이 수는 R(m,n) 보다 크다고 할 수 있다. . □

이제 R(4,4) 가 18임을 증명하자.

Ramsey Theorem 에 의해 R(4,4) ≤ R(4,3) + R(3,4) 이 성립하고 Lemma 2와 Lemma 3에 의해 R(4,4) ≤ R(4,3)+R(3,4) = 2R(4,3) = 18 이 성립한다. R(4,3)>17 임을 보이기 위해선 R=17 일 때, 반례가 있음을 보이면 된다. 이것은 그다지 어렵지 않기 때문에 숙제로 남긴다. 여러분들이 한번 찾아보길 바란다.

이상 우리는 간단하게나마 Ramsey Number 에 대해서 알고 몇 가지 경우에 대해서 Ramsey Number 를 직접 찾고 증명해 보았다. 또한 우리는 R(4,4)=18 임을 증명할 수 있었다. 마지막으로 현재까지 밝혀진 Ramsey Number 에 대한 표는 다음과 같다.

l k	3	4	5	6	7	8
3	6	9	14	18	23	27/30
4		18	25/28	34/44
5			42/55	51/94
6				69/102

References

1. 「Ramsey Theory」, Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer (1980 ; John Wiley & Sons, Inc)

2. 「Discrete Mathematics and Its Applications」, Kenneth H. Rosen  (4th ed ; VAGA, New York)

출처 : http://math.kaist.ac.kr/%7Edeneb/study/Ramsey_Numbers.htm