램지 이론
위키백과, 무료 백과사전
위키백과, 무료 백과사전
램지 이론(Ramsey theory)은 수학적 구조의 크기에 따라 나타나는 특정한 질서를 연구하는 분야이다. 영국의 철학자이자 수학자인 프랭크 램지(Frank P. Ramsey)의 램지 정리에서 이름을 따왔다. 흔히 조합론의 한 분야로 분류되며, 그래프 이론, 집합론 등과도 연관이 있다.
유한 램지 정리는 다음과 같은 정리이다. 임의의 자연수열 n1, n2, n3, ..., nc가 주어져 있고 완전 그래프의 각 변마다 c가지 색 중 하나의 색을 칠한다 하자. 이때 완전 그래프의 크기만 충분히 크면 그래프에는 어떤 i번째 색에 대해 ni개의 점으로 이루어진 단색(單色)의 완전 부분 그래프(즉 클릭)이 반드시 존재한다. 요컨대 램지 이론에서는 이 정리에서 완전 그래프가 정확히 어느 정도로 커야 주어진 조건이 만족되는가를 탐구하며, 그러한 문턱값을 램지 수(Ramsey number)라고 한다. 예를 들어 위의 예시에서 c=2, n1=n2=3이면 그 램지 수는 6이다.
이외에 램지 이론의 특징적 정리로는 다음과 같은 것들이 있다:
![]() |
이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.