램지 이론

1. 개요[편집]

---

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

1.1. 램지 정리[편집]

---

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