램지의 정리: 두 판 사이의 차이

충분히 큰 [[완전 그래프]]의 변(edge)을 색칠하게 되면, 동일한 색의 변으로만 구성된 완전 그래프가 포함되어 있다. 양의 정수 (''r'',''s'')에 대해, 정수 ''R''(''r'',''s'')이 존재하는데, ''R''(''r'',''s'') 이상의 꼭지점(vertex)을 가지는 [[완전 그래프]]의 변을 ''빨강''과 ''파랑'' 두가지 색으로 칠하게 되면, 그 그래프는 ''r''개 이상의 꼭지점을 가지는 파랑 완전 그래프나 ''s''개 이상의 꼭지점을 가지는 빨강 완전 그래프, 둘 중의 어느 하나를 부분 그래프로 포함하게 된다. 이것을 '''램지의 정리'''라고 한다. 당연히 정수 ''R''(''r'',''s'')은 ''r''과 ''s''에 의존한다. 세 가지 이상의 색이 칠해진 경우, 즉 ''R''(''r'',''s'',''t'',...)도 연구되고 있다.

 

[[그림:RamseyTheory_K5_no_mono_K3.PNG|right|A 2-coloring of K_5 with no monochromatic K_3]]

6개의 꼭지점을 가지는 완전 그래프의 각 변을 빨강과 파랑으로 칠한다. 한 꼭지점 ''v''를 보면, 그 꼭지점에는 5개의 변이 연결되어 있다. [[비둘기집 원리]]에 의해, 적어도 그 중 3개는 같은 색이다. 그 색을 파랑이라고 가정 하고, 그 3개의 변에 연결된 꼭지점을 각각 ''r'', ''s'', ''t''라고 하자.

한편, ''K''₅를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, ''R''(3,3) > 5 이다. 결론적으로 ''R''(3,3)=6 이다.

 

 

{| class="wikitable" style="text-align:center;"