램지의 정리: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
|||
1번째 줄:
충분히 큰 [[완전 그래프]]의 변(edge)
==예제: ''R''(3,3)=6==
[[그림: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''라고 하자.
만약 변 (''r'', ''s''), 변 (''r'', ''t''), 변 (''s'', ''t'') 한편, ''K''<sub>5</sub>를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, ''R''(3,3) > 5 이다. 결론적으로 ''R''(3,3)=6 이다.
다음은 알려져 있는 몇 가지 경우의 램지 수이다. 대부분의 경우 램지 수의 정확한 값은 거의 알려져 있지 않다.
{| class="wikitable"
! ''r'' \ ''s''
! 1
! 2
! 3
! 4
! 5
! 6
! 7
! 8
! 9
! 10
|- align="center"
! 1
| 1
|
|
|
|
|
|
|
|
|
|- align="center"
! 2
| 1
| 2
|
|
|
|
|
|
|
|
|- align="center"
! 3
| 1
| 3
| 6
|
|
|
|
|
|
|
|- align="center"
! 4
| 1
| 4
| 9
| 18
|
|
|
|
|
|- align="center"
! 5
| 1
| 5
| 14
| 25
| 43~49
|
|
|
|
|
|- align="center"
! 6
| 1
| 6
| 18
| 35~41
| 58~87
| 102~165
|
|
|
|
|- align="center"
! 7
| 1
| 7
| 23
| 49~61
| 80~143
| 113~298
| 205~540
|
|
|
|- align="center"
! 8
| 1
| 8
| 28
| 56~84
| 101~216
| 127~495
| 216~1031
| 282~1870
|
|
|- align="center"
! 9
| 1
| 9
| 36
| 73~115
| 125~316
| 169~780
| 233~1713
| 317~3583
| 565~6588
|
|- align="center"
! 10
| 1
| 10
| 40~43
| 92~149
| 143~442
| 179~1171
| 289~2826
| ≤ 6090
| 580~12677
| 798~23556
|}
이 표는 [[Stanisław Radziszowski]]의 논문[http://www.combinatorics.org/Surveys/index.html]에서 가져왔다.
[[Category:그래프 이론]]
|