본문으로 이동

램지 이론

위키백과, 우리 모두의 백과사전.

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

램지 정리

[편집]

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

같이 보기

[편집]