램지 이론

램지 이론(Ramsey theory)은 수학적 구조의 크기에 따라 나타나는 특정한 질서를 연구하는 분야이다. 영국의 철학자이자 수학자인 프랭크 램지(Frank P. Ramsey)의 램지 정리에서 이름을 따왔다. 흔히 조합론의 한 분야로 분류되며, 그래프 이론, 집합론 등과도 연관이 있다.

램지 정리

유한 램지 정리는 다음과 같은 정리이다. 임의의 자연수열 n₁, n₂, n₃, ..., n_c가 주어져 있고 완전 그래프의 각 변마다 c가지 색 중 하나의 색을 칠한다 하자. 이때 완전 그래프의 크기만 충분히 크면 그래프에는 어떤 i번째 색에 대해 n_i개의 점으로 이루어진 단색(單色)의 완전 부분 그래프(즉 클릭)이 반드시 존재한다. 요컨대 램지 이론에서는 이 정리에서 완전 그래프가 정확히 어느 정도로 커야 주어진 조건이 만족되는가를 탐구하며, 그러한 문턱값을 램지 수(Ramsey number)라고 한다. 예를 들어 위의 예시에서 c=2, n₁=n₂=3이면 그 램지 수는 6이다.

결과

이외에 램지 이론의 특징적 정리로는 다음과 같은 것들이 있다:

• 판데르바르던의 정리(Van der Waerden's theorem): 어떠한 자연수 c, n이 주어지더라도, 연속하는 V개의 자연수를 c개의 색으로 어떻게 칠하더라도 한가지 색으로 이루어진 길이 n의 등차수열이 존재하도록 하는 자연수 V가 존재한다.
• 헤일스-주에트 정리(Hales-Jewett theorem): 어떠한 자연수 c, n이 주어지더라도 H차원 n×n×...×n 초입방체의 셀들을 c개의 색으로 나누어칠할 때, 속해있는 모든 셀이 같은 색으로 칠해진 길이 n의 줄이 최소 1개는 존재하도록 하는 자연수 H가 존재한다. 즉, 여럿이 하는 n렬 틱택토 게임은 충분히 큰 차원에서 플레이한다면 n이 아무리 크거나 플레이어가 아무리 많아도 절대 무승부로 끝나지 않는다. Hales-Jewett 정리는 Van der Waerden's 정리를 함의한다.

같이 보기

• 그래프 이론
• 램지의 정리
• 굿스타인의 정리
• 프랭크 램지
• 바르털 레인더르트 판데르바르던