주 메뉴 열기

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

결과편집

램지 이론의 실마리가 되는 두 정리로는 다음을 들 수 있다:

  • 판데르바르던의 정리(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 정리를 함의한다.

같이 보기편집