조합[램지의 정리] 2-3

고든 램지, 출처:한국경제

램지의 정리를 처음 보는 분들이라면 고든 램지를 떠올렸을 수도 있을 것 같다. 하지만 이번에 배울 램지의 정리는 고든 램지에 당연히 아무 관련없는 정리이다.

램지의 정리에 대해 설명하기에 앞서, 완전그래프 Kn에 대해 먼저 알고 있어야 한다. Kn은 n개의 점이 존재하고 어떤 2개의 점을 잡아도 점과 점이 연결되어 있는 상태를 말한다.

K4, 출처:위키백과

위에 보이는 사진이 바로 K4 완전그래프이다. 4개의 점이 존재하고 어떤 2개의 점을 잡아도 직접적으로 이어져 있는 것이 확인된다.

R(a,b)=n이라면 Kn의 각 선분을 2가지 색으로 임의로 색칠시 항상 Ka나 Kb가 존재하게 된다는 뜻이다.

백문이불여일견이라고 아래의 예시로 이해를 도와보겠다.

 

※주의사항:램지이론은 완전그래프에서만 사용할 수 있다.

 

#1.9명의 사람 가운데 서로 아는 세 사람이 있거나 서로 전혀 모르는 4사람이 있음을 증명하여라. 9는 더 작은 수로 바뀔 수 없음을 보여라.

이 문제는 R(3,4)=9임을 증명하라는 문제와 다름이 없다.

램지이론을 증명할 때에는 증명과정을 크게 2가지로 나누어 설명한다.

K9의 각 선분을 빨,파로 임의로 색칠시 항상 빨강 K3나 파랑 K4가 존재한다. 

 

①R(3,4)≤9

비둘기집의 원리에 의해 9개의 점 중에 하나를 잡자.

a와 빨강색으로 연결된 4개의 원소를 보라. 비둘기집의 원리에 의해 4개 이상의 선이 같은 색인 경우가 생긴다.

빨강색으로 연결된 4개의 원소 사이는 선을 연결시 빨강색이 있으면 빨 K3가 생겨 모순이 된다. 따라서 저 4개의 원소 사이에서는 파랑색 선분만 존재해야 한다. 그런데 그렇게 되면 파 K4가 생긴다. 따라서 R(4,3)=9

 

②R(3,4)>8

R(3,4)=8인 경우, 반례가 생긴다.(7각형이 있을 때 그 안에 점이 존재하여 내부의 점과 나머지 7개의 점 사이의 선과 7각형의 변이 빨강색인 경우가 반례)

 

램지수는 다음의 식이 성립한다.

R(r,s)≤R(r-1,s)+R(r,s-1)

R(r,s)≤_r+s-2C_r-1