램지 이론 (Ramsey Theory)
한 줄 정의: 구조가 충분히 커지면 규칙적인 부분이 반드시 나타남을 다루는 조합론 분야입니다.
쉽게 풀면
여섯 명이 모이면 서로 아는 사이인 세 사람이나 서로 모르는 사이인 세 사람이 반드시 존재합니다. 사람 수가 충분하면 어떻게 관계가 얽혀 있든 질서 있는 부분을 피할 수 없다는 것이 램지 이론의 핵심입니다. 완전히 무질서한 구조는 충분히 크면 존재할 수 없다는 뜻입니다.
왜 중요한가
조합론과 그래프이론에서 존재성을 보장하는 대표적인 정리군이며, 수리논리, 이론전산, 수론의 여러 결과와 연결됩니다. 알고리즘의 하한을 증명하거나 무작위 구조의 필연적 패턴을 논할 때 인용됩니다.
논문에서는 이렇게 쓰입니다
"램지 이론의 결과를 이용하여 정점 수가 임계값을 넘으면 단색 부분그래프가 반드시 존재함을 보였다."
조금 더 깊게 보면
램지 수 R(s, t)는 완전그래프의 변을 두 색으로 칠할 때 한 색의 s개 완전부분그래프나 다른 색의 t개 완전부분그래프가 반드시 나타나는 최소 정점 수입니다. 존재성은 증명되었지만 정확한 값은 매우 작은 경우 외에는 알려져 있지 않으며, R(5,5)조차 미해결입니다. 에르되시가 상한과 하한을 증명하며 도입한 확률론적 방법은 조합론 전반의 표준 기법이 되었습니다. 정수 분할에 대한 판 데르 바르덴 정리나 슈어 정리도 같은 계열의 결과입니다.
주의할 점
램지 이론은 어떤 크기 이상이면 반드시 존재한다는 존재 정리일 뿐, 그 구조를 실제로 찾아 주는 방법을 제공하지는 않습니다. 조세이론의 램지 원칙과는 이름만 같습니다.