'램지의 2색 정리'라고도 알려진 이는 1990년대 영국의 수학적 논리학자 시타판(Sitapan)이 제안한 추측이다. 조합 수학에서 Ramsey의 정리는 다음 문제를 해결하는 것입니다. n명 중에서 k명이 서로 알거나 l명이 서로 몰라야 하는 최소 수 n을 찾는 것입니다. 이 정리는 1930년 논문 On a Problem in Formal Logic에서 R(3,3)=6을 증명한 Frank Plumpton Ramsay의 이름을 따서 명명되었습니다. 램지 수의 정의 램지 수는 그래프 이론의 언어로 두 가지 설명을 갖습니다. 모든 N-상단 그래프에 대해 k 상단을 포함하는 그룹 또는 l 상단의 독립적인 집합입니다. 이러한 특성을 갖는 가장 작은 자연수 N을 램지 수(Ramsey number)라고 하며 R(k,l)로 기록됩니다. 이는 색칠 이론에서 다음과 같이 설명됩니다. 전체 그래프 Kn의 임의의 2-에지 색칠(e1, e2)에 대해 Kn[e1]은 k차 부분완전 그래프를 포함하고 Kn[e2]는 l차 부분완전 그래프를 포함하며, 이 조건을 만족하는 가장 작은 n을 램지 수라고 합니다. (참고: Ki는 그래프 이론 표기법에 따라 i차 완전 그래프를 나타냅니다.) Ramsey는 주어진 양의 정수 k와 l에 대해 R(k,l)에 대한 답이 고유하고 유한하다는 것을 증명했습니다. Ramsey 수는 두 개 이상의 숫자로 일반화될 수도 있습니다. 전체 그래프 Kn의 각 모서리에 대해 각 모서리는 kn에 각각 e1, e2, e3,...,er로 기록되는 r 색상 중 하나로 임의로 칠해집니다. 색상 e1의 l1차 하위 완성 그래프, 색상 e2의 l2차 하위 완성 그래프...또는 색상 er의 lr차 하위 완성 그래프가 있어야 합니다. 조건을 만족하고 가장 작은 숫자 n은 R(l1,l2,l3,...,lr;r)로 기록됩니다. 알려진 Ramsey 수 또는 Ramsey 수의 상한과 하한은 거의 없습니다. Paul Adish는 Ramsey 수를 찾는 어려움을 설명하기 위해 다음과 같은 이야기를 사용한 적이 있습니다. "외계 군대가 지구에 상륙하는 것을 상상해 보십시오. R(5, 5)가 필요합니다. 그렇지 않으면 지구가 파괴됩니다. 이 경우 우리는 R(6,6)의 값을 찾기 위해 모든 컴퓨터와 수학자들을 모아야 합니다. 이 외계인 그룹을 파괴하도록 노력합시다.” 공식: R(1,s)=1, R(2,s)=s, R(l1,l2,l3,...,lr;r.)=R(l2,l1,l3,..., lr;r)=R(l3,l1,l2,...,lr;r) (li의 순서를 변경해도 Ramsey의 값은 변경되지 않습니다). r,s 3 4 5 6 7 8 9 103 6 9 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 11717 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 28268 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780 233 – 1713 – 3583 565 – 6588 580 – 1267710 40 – 43 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556R(3,3,3)=17 R(3,3)이 6과 같음을 증명합니다. 증명: 다음의 완전한 그래프에서 K6, 각 면이 빨간색이나 파란색으로 칠해져 있으면 빨간색 삼각형이나 파란색 삼각형이 있어야 합니다.
다른 끝점에 연결된 5개의 모서리가 있는 끝점 P를 무작위로 선택합니다. 비둘기집 원리에 따르면, 세 변 중 적어도 두 변은 같은 색을 띠지만, 이 색은 빨간색이 됩니다. P를 제외한 이 세 모서리의 세 끝점 중 서로 연결되는 세 개의 모서리가 있습니다. 이 세 변 중 하나라도 빨간색이면 이 변의 두 끝점과 P에 연결된 두 변이 빨간색 삼각형을 형성합니다. 세 변 중 하나라도 빨간색이 아니면 파란색이어야 하므로 파란색 삼각형을 형성합니다. 그리고 K5에는 반드시 빨간색 삼각형이나 파란색 삼각형이 있는 것은 아닙니다. 각 끝점과 인접한 두 끝점 사이의 선은 빨간색이고 다른 두 끝점을 연결하는 선은 파란색입니다. 이 정리의 대중적인 버전은 우정 정리입니다.