램지의 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
4. 알려진 램지 수
5. 점근적 성질
6. 유도 램지
7. 확장
8. 역사
9. 선택 공리와의 관계
참조

1. 개요

램지의 정리는 주어진 조건(색깔의 수, 초변의 크기, 주어진 색깔의 초변의 수)을 만족하는 양의 정수(램지 수)가 존재한다는 정리이다. 이 정리는 그래프 이론으로 해석될 수 있으며, 완전 초그래프의 초변을 여러 색깔로 칠할 때 특정 크기의 동색 클릭이 존재함을 보장한다. 램지 수는 램지 정리에 따라 존재하며, 일반적으로 정확한 값은 알려져 있지 않고 상한과 하한만 알려져 있다. 램지 정리는 무한 그래프, 하이퍼그래프, 유향 그래프 등으로 확장될 수 있으며, 유도 램지 수라는 개념도 존재한다. 램지 정리는 1930년 프랭크 램지에 의해 증명되었으며, 램지 이론의 시초로 여겨진다. 또한, 램지 정리는 선택 공리와의 관계에서 증명 강도에 차이를 보인다.

더 읽어볼만한 페이지

그래프 이론 정리 - 4색 정리
4색 정리는 평면을 나눈 영역을 인접한 영역과 다른 색으로 칠할 때 필요한 최소 색의 수가 4개라는 정리로, 그래프 이론을 통해 추상화되어 평면 그래프의 4-채색 가능성을 나타내며, 컴퓨터를 이용한 증명과 그에 대한 논란, 그리고 재증명이 이루어졌다.
그래프 이론 정리 - 최대 유량 최소 컷 정리
최대 유량 최소 컷 정리는 네트워크의 최대 유량과 최소 컷의 용량이 같다는 것을 나타내며, 포드-풀커슨 알고리즘으로 증명되고 다양한 실생활 문제 해결에 기여한다.
램지 이론 - 비둘기집 원리
비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
램지 이론 - 세메레디의 정리
세메레디의 정리는 양의 상부 밀도를 갖는 자연수 부분집합이 임의 길이의 등차수열을 포함한다는 내용으로, 세메레디 엔드레가 증명하고 힐렐 퓌르스텐베르크가 다른 증명을 제시했으며, 반 데르 바르덴 정리의 일반화이자 그린-타오 정리와 연관된다.

램지의 정리
개요
분야	조합론
발견자	프랭크 P. 램지
발견 연도	1930년
설명	충분히 큰 구조는 반드시 정규성을 가진 부분 구조를 포함한다.
램지 수
정의	R(r, s)는 임의의 그래프에 대해 r차 완전 그래프 또는 s개의 독립 집합을 포함하도록 하는 최소 정점의 수이다.
값	R(3, 3) = 6, R(4, 2) = 4, R(4, 3) = 9, R(5, 3) = 14
일반화
일반화된 램지 수	R(n₁, …, nc)는 c개의 색으로 변을 색칠한 완전 그래프에서 각 색 i에 대해 크기가 ni인 단색 완전 부분 그래프가 존재하도록 하는 최소 정점의 수이다.

2. 정의

램지 정리에 따르면, 특정 조건을 만족하는 양의 정수(램지 수)가 존재한다. 램지 수는 주어진 색깔의 수, 초변의 크기, 그리고 각 색깔에 해당하는 초변의 수를 기반으로 결정된다.

램지 수는 완전 m-초그래프의 초변들을 c개의 색깔로 색칠했을 때, 특정 색깔과 크기를 가진 클릭(부분 그래프)이 반드시 존재하도록 하는 꼭짓점의 최소 개수를 의미한다. 일반적으로 c=m=2인 경우, 램지 수는 R(r,s)로 표기된다.

램지 정리는 비둘기집 원리의 일반화로 볼 수 있는데, m=1인 경우가 비둘기집 원리와 동일하다. 또한, c=1인 경우에는 램지 정리가 자명하게 성립한다. m=c=2일 때, R(1,n)=R(n,1)=1, R(2,n)=R(n,2)=n과 같은 램지 수들은 자명하다.^[1]

2. 1. 기본 정의

집합

S

의 크기가

m

인 부분 집합들의 집합을

\textstyle\binom Sm

으로 표기한다.

다음과 같은 조건들이 주어졌다고 가정한다:

양의 정수 $c$ (색깔의 수)
양의 정수 $m$ (초변의 크기)
양의 정수 $n_1,\dots,n_c$ (주어진 색깔의 초변의 수)

'''램지의 정리'''에 따르면, 다음 조건을 만족시키는 양의 정수

R(n_1,\dots,n_m;c,m)

(램지 수)가 존재한다.

임의의 집합

S

및

\textstyle\binom Sm

의

c

개 조각으로의 분할

\textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c

에 대하여, 만약

|S|\ge R(n_1,\dots,n_c;c,m)

라면, 다음 조건을 만족시키는 부분 집합

T\subseteq S

와

i\in\{1,\dots,c\}

가 존재한다.

:

|T|\ge n_i

이며,

\textstyle\binom Tm\subseteq E_i

이다.

이는 그래프 이론으로 해석할 수 있다.

m

-'''초그래프'''(hypergraph^영어)는 꼭짓점과

m

-'''초변'''(hyperedge^영어)들로 구성된 조합론적 구조이며, 여기서

m

-초변은

m

개의 꼭짓점들로 구성된 집합이다. (2-초그래프는 그래프와 같다.) 임의의 꼭짓점 집합

S

에 대하여, 초변 집합이

\textstyle\binom Sm

인 초그래프를 '''완전

m

-초그래프'''라고 한다. (완전 2-초그래프는 완전 그래프이다.) 이 경우,

\textstyle\binom Sm

의

c

개 조각으로의 분할은 완전 초그래프의 초변들을

c

개의 색깔로 색칠하는 것과 같다. 이때, 위와 같은 성질을 갖는

T

는 동색의 '''클릭'''이라고 한다.

램지 정리에 따르면,

R(n_1,\dots,n_c;c,m)

개 이상의 꼭짓점을 가진 완전

m

-초그래프의 초변들을

c

개의 색깔로 색칠하면, 1번 색깔의 크기

n_1

의 클릭, 2번 색깔의 크기

n_2

의 클릭, ……, 또는

c

번 색깔의 크기

n_c

의 클릭이 존재한다.

램지 정리에 따라 존재하는 양의 정수

R(n_1,\dots,n_c;c,m)

을 '''램지 수'''(Ramsey number^영어)라고 한다.

c=m=2

일 경우, 통상적으로

R(r,s;2,2)=R(r,s)

로 표기한다.

2. 2. 무한 램지 정리

infinite Ramsey theorem^영어라고도 불리는 무한 램지 정리는 유한 램지 정리의 확장판이다.

임의의 양의 정수 m, c와 가산 무한 집합 S, 그리고 S에서 m개의 원소를 뽑아 만들 수 있는 모든 부분집합(m차 조합)을 c개의 부분집합(E₁부터 E_c까지)으로 분할했을 때, S의 어떤 무한 부분집합 T와 1부터 c 사이의 어떤 수 i에 대해, T에서 m개의 원소를 뽑아 만든 모든 부분집합이 E_i에 포함되도록 할 수 있다.

이는 $$R(\aleph_0,\aleph_0,\dots,\aleph_0;m,c) = \aleph_0$$ 로 표현할 수 있다.

무한 그래프에 대한 램지 정리는 보통 집합론 용어로 표현되는데, "램지 정리"라고도 불린다. 이 정리에 따르면, 무한 집합 X에서 n개의 원소를 가진 부분집합들을 c가지 색으로 칠했을 때, X의 무한 부분집합 M이 존재하여 M에서 n개의 원소를 뽑아 만든 모든 부분집합이 같은 색을 가지게 된다.^[44]

에르되스-더쉬닉-밀러 정리는 무한 그래프에 대한 램지 정리의 더 강력한 형태이다. 이 정리에 따르면, 모든 무한 그래프는 가산 무한 독립 집합이나, 원래 그래프와 같은 기수를 가진 무한 클릭을 포함한다.^[45]

유한 램지 정리는 귀류법과 컴팩트성 논증을 통해 무한 램지 정리로부터 유도할 수 있다.^[46]

2. 3. 자명한 경우

\textstyle\binom S1

는

S

와 표준적으로 일대일 대응하므로, 완전 1-초그래프는 집합과 같은 개념이다.

m=1

일 경우 램지 정리는 비둘기집 원리와 같다. 즉, 램지 정리는 비둘기집 원리의 일반화이다.

c=1

일 경우, 램지 정리는 자명하게 성립한다.

m=c=2

일 경우 다음과 같은 램지 수들은 자명하다.

$R(1,n)=R(n,1)=1$
$R(2,n)=R(n,2)=n$ ^[1]

3. 성질

램지 수의 성질, 특히 `r = s = 2`일 때의 램지 수 `R(k, l) = R₂(k, l)`에 대해 많은 결과가 알려져 있다.

다음 결과가 알려져 있다.

`R(r, s) ≤ R(r-1, s) + R(r, s-1)`이다.^[1]
증명: `R(r − 1, s) + R(r, s − 1)`개의 정점을 가진 완전 그래프를 두 가지 색(파란색, 빨간색)으로 칠한다. 그래프에서 정점 `v`를 선택하고, 나머지 정점을 두 집합 `M`과 `N`으로 나눈다. 정점 `w`에 대해, 변 `(vw)`가 파란색이면 `w`는 `M`에, 빨간색이면 `w`는 `N`에 속한다. 그래프는 `R(r-1,s) + R(r,s-1) = |M| + |N| + 1`개의 정점을 가지므로, `|M| ≥ R(r-1, s)`이거나 `|N| ≥ R(r, s-1)` 중 하나가 성립한다. 전자의 경우, `M`이 빨간색 `Kₛ`를 가지면 원래 그래프도 마찬가지이며 증명이 끝난다. 그렇지 않으면 `M`은 파란색 `K`를 가지므로 `M ∪ {v}`는 파란색 `K`를 가진다. 후자의 경우도 유사하다.
`R(r − 1, s)`와 `R(r, s − 1)`이 모두 짝수이면, `R(r,s) ≤ R(r-1,s) + R(r,s-1) - 1`이다.^[2]
증명: `p = R(r − 1, s)`와 `q = R(r, s − 1)`가 모두 짝수라고 가정한다. `t = p + q − 1`로 놓고, `t`개의 정점을 가진 그래프를 두 가지 색으로 칠한다. `dᵢ`가 파란색 부분 그래프에서 `i`번째 정점의 차수이면, 핸드셰이킹 보조정리에 의해 `Σdᵢ`는 짝수이다. `t`가 홀수이므로, 짝수인 `dᵢ`가 존재한다. 일반성을 잃지 않고, `d₁`이 짝수이고, `M`과 `N`이 각각 파란색 및 빨간색 부분 그래프에서 정점 1에 인접한 정점이라고 가정하자. 그러면 `|M| = d₁`과 `|N| = t - 1 - d₁`는 모두 짝수이다. 비둘기집 원리에 의해, `|M| ≥ p - 1` 또는 `|N| ≥ q` 중 하나가 성립한다. `|M|`이 짝수이고 `p – 1`이 홀수이므로, `|M| ≥ p` 또는 `|N| ≥ q` 중 하나가 성립한다. `|M| ≥ p = R(r-1, s)`라고 가정하면, `M` 부분 그래프는 빨간색 `Kₛ`를 가지며 증명이 완료되거나, 정점 1과 함께 파란색 `K`를 가지며 파란색 `Kᵣ`를 만든다. `|N| ≥ q = R(r, s-1)`인 경우도 유사하게 처리된다.
대칭에 의해, `R(m, n) = R(n, m)`이다.
`R(r, s)`에 대한 상한은 정리의 증명에서 추출할 수 있으며, 다른 논증은 하한을 제공한다.^[3]
가장 조밀한 하한과 상한 사이에는 큰 격차가 있으며, `R(r, s)`의 정확한 값을 알고 있는 `r`과 `s`의 수는 매우 적다.
`R(r, s)`에 대한 하한 `L`을 계산하려면 파란색/빨간색으로 그래프 `Kₗ₋₁`를 채색하여 파란색 `Kᵣ` 부분 그래프와 빨간색 `Kₛ` 부분 그래프가 없도록 해야 한다.
상한을 설정하는 것은 매우 어렵다. 반례가 없음을 확인하기 위해 가능한 모든 채색을 확인하거나, 부재에 대한 수학적 논증을 제시해야 한다.
에르되시는 외계인이 지구에 착륙하여 `R(5, 5)`의 값을 요구하면 모든 컴퓨터와 수학자를 동원해야 하지만, `R(6, 6)`를 요구하면 외계인을 파괴해야 한다고 조엘 스펜서에게 말했다.^[4]
무차별 대입법을 사용하면 모든 가능한 그래프를 검색하는 복잡성은 `c`개의 채색과 최대 `n`개의 노드에 대해 `O(cⁿ²) `이다.^[5]
양자 컴퓨터는 고전적인 컴퓨터에 비해 이차적인 속도 향상만 보이므로, 계산 시간은 노드 수에 대해 여전히 지수적이다.^[6]^[7]
`R(3, 3) = 6`이다.
모든 `s`에 대해 `R(s, 2) = s`이다.
`R(4, 3) ≤ R(4, 2) + R(3, 3) − 1 = 9`이고, `R(4, 4) ≤ R(4, 3) + R(3, 4) ≤ 18`이다.
`(4, 4, 16)` 그래프는 두 개, `(4, 4, 17)` 그래프(차수 17의 페일리 그래프)는 하나뿐이다.^[3] 따라서 `R(4, 4) = 18`이다.
`R(4, 5) = 25`는 1995년 브렌단 맥케이와 스타니스와프 라지시조프스키에 의해 밝혀졌다.^[8]
`R(5, 5)`의 정확한 값은 알려져 있지 않지만, 43^[9]과 46^[10] 사이에 있다.
1997년 맥케이, 라지시조프스키, 엑소는 `R(5, 5) = 43`이라고 추측했다. 그들은 656개의 `(5, 5, 42)` 그래프를 구성했으며, 어떤 것도 `(5, 5, 43)` 그래프로 확장될 수 없었다.^[11]
`r, s > 5`인 `R(r, s)`의 경우 약한 경계만 사용할 수 있다. `R(6, 6)` 및 `R(8, 8)`의 하한은 각각 1965년과 1972년 이후 개선되지 않았다.^[12]

`r, s ≤ 10`인 `R(r, s)`는 아래 표에 나와 있다. 정확한 값을 알 수 없는 경우, 가장 잘 알려진 경계가 나열되어 있다. `r < 3`인 `R(r, s)`는 모든 `s` 값에 대해 `R(1, s) = 1` 및 `R(2, s) = s`로 주어진다.

램지 수 `R(r, s)`^[13] 에 대한 값/알려진 경계 범위
r\s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40–41^[14]
4	1	4	9	18	25^[8]	36–40	49–58	59^[15]–79	73–105	92–135
5	1	5	14	25^[8]	43–46^[16]	59^[17]–85	80–133	101–193	133–282	149^[15]–381
6	1	6	18	36–40	59^[17]–85	102–160	115^[15]–270	134^[15]–423	183–651	204–944
7	1	7	23	49–58	80–133	115^[15]–270	205–492	219–832	252–1368	292–2119
8	1	8	28	59^[15]–79	101–193	134^[15]–423	219–832	282–1518	329–2662	343–4402
9	1	9	36	73–105	133–282	183–651	252–1368	329–2662	565–4956	581–8675
10	1	10	40–41^[14]	92–135	149^[15]–381	204–944	292–2119	343–4402	581–8675	798–16064

램지 수 연구 개발에 대한 표준 설문 조사는 스타니스와프 라지시조프스키의 ''전자 조합 저널''의 ''동적 설문 1''이다.

`R(r, s) ≤ ` (귀납적 증명).
`r = s`일 때, `R(s, s) ≤ (1 + o(1))4ˢ / √πs`이다.
`R(s, s) ≥ (1 + o(1))s / (√2e) * 2ˢ/²` (1947년 에르되시).
대각 램지 수에 대한 가장 잘 알려진 하한과 상한은 `[1 + o(1)] √2s/e * 2ˢ/² ≤ R(s, s) ≤ s⁻⁽ᶜ ˡᵒᵍ ˢ⁾/⁽ˡᵒᵍ ˡᵒᵍ ˢ⁾ 4ˢ`이다.
2023년, Campos, Griffiths, 모리스, 사하스라부데는 상한을 `R(s,s) ≤ (4-ε)ˢ`로 개선했다.^[18]^[19]
비대각 램지 수 `R(3, t)`는 `t²/log t`의 차수를 갖는다.
`R(3, t)`에 대한 상한은 아지타이, 콤로스, 세메레디에 의해 주어지고,^[20] 하한은 김에 의해 얻어졌다.^[21]
일반적인 비대각 램지 수에 대한 점근적 하한은 "H-free process"를 연구하여 설정되었다.^[24]

`c'ₛ t⁽ˢ⁺¹⁾/²/ (log t)⁽ˢ⁺¹⁾/² ⁻ ¹/⁽ˢ⁻²⁾ ≤ R(s, t) ≤ cₛ tˢ⁻¹ / (log t)ˢ⁻²`.

`s=4`의 경우, 2023년 논문은 하한을 `c'ₛ t³/ (log t)⁴`로 개선했다.^[25]^[26]

4. 알려진 램지 수

대부분의 경우 램지 수의 정확한 값은 거의 알려져 있지 않고, 범위의 형태로만 확인되어 있다.^[56]

램지 수 R(r, s) (r, s ≤ 10)의 값/알려진 경계 범위^[12]^[13]
r\s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40–42^[14]
4	1	4	9	18	25^[8]	36–41	49–61	59^[15]–84	73–115	92–149
5	1	5	14	25^[8]	43–48^[16]	59^[17]–85	80–143	101–216	133–316	149^[15]–381
6	1	6	18	36–41	59^[17]–85	102–165	115^[15]–270	134^[15]–423	183–651	204–944
7	1	7	23	49–61	80–143	115^[15]–270	205–540	219–832	252–1368	292–2119
8	1	8	28	59^[15]–84	101–216	134^[15]–423	219–832	282–1870	329–3583	343–4402
9	1	9	36	73–115	133–316	183–651	252–1368	329–3583	565–6588	581–12677
10	1	10	40–42^[14]	92–149	149^[15]–381	204–944	292–2119	343–4402	581–12677	798–23556

$c\ge3$ 일 경우, 알려진 유일한 (자명하지 않은) 램지 수는

: $R(3,3,3;3,2)=17$

이다.

이 외에도, 다음의 평가가 알려져 있다.

51≤ ''R''₄(3, 3, 3, 3)≤ 62
162≤ ''R''₅(3, 3, 3, 3, 3)≤ 307
538≤ ''R''₆(3, 3, 3, 3, 3, 3)≤ 1838
1682≤ ''R''₇(3, 3, 3, 3, 3, 3, 3)≤ 12861
''R''_''r''(3, 3, ..., 3)≤ ''r''(''R''_{''r'' -1}(3, 3, ..., 3)-1)+2.

5. 점근적 성질

R(s, s)^영어 ≤ (1 + o(1)) 그리고 R(s, s)^영어 ≥ (1 + o(1)) (s / √2e) 2^s/2 이 성립한다. 비대각 램지 수 R(3, t)^영어는 의 차수를 갖는다.

램지 수 에 대한 상한은 정리 증명에서 추출할 수 있으며, 다른 논증은 하한을 제공한다. 폴 에르되시는 확률적 방법을 사용하여 지수 하한을 얻었다. 그러나 가장 조밀한 하한과 상한 사이에는 큰 격차가 있으며, 의 정확한 값을 알고 있는 과 의 수는 매우 적다.

에 대한 하한 을 계산하려면 파란색/빨간색으로 그래프 를 채색하여 파란색 부분 그래프와 빨간색 부분 그래프가 없도록 해야 한다. 이러한 반례를 "램지 그래프"라고 한다. 브렌던 맥케이는 알려진 램지 그래프 목록을 유지한다.^[3]

에 대한 상한과 하한은 다음과 같다.

: \leq R(s, s) \leq s^{-(c \log s)/(\log \log s)} 4^s,}}

각각 스펜서와 콘론에 의해 제시되었다.

비대각 램지 수 는 의 차수를 갖는 것으로 알려져 있다.

에 대한 점근적 하한은 다음과 같다.

:}{(\log t)^{\frac{s + 1}{2} - \frac{1}{s - 2}}} \leq R(s, t) \leq c_s \frac{t^{s - 1}}{(\log t)^{s - 2}}.}}

6. 유도 램지

램지 정리에는 덜 알려져 있지만 흥미로운 유사 개념이 유도 부분 그래프에 적용된다. 이는 단색 부분 그래프를 찾는 대신, 단색 유도 부분 그래프를 찾는 것이다. 완전 그래프에만 초점을 맞추는 것으로는 충분하지 않은데, 완전 부분 그래프가 존재한다고 해서 반드시 유도 부분 그래프가 존재하는 것은 아니기 때문이다.^[31]^[32]^[33]

6. 1. 정의

그래프 H^영어가 n개의 꼭짓점을 가진다고 하자. 그러면, 두 가지 색을 사용하여 G^영어의 변을 색칠할 때 단색의 유도된 복사본 H^영어 (즉, H^영어와 동형이고 그 변들이 단색인 G^영어의 유도된 부분 그래프)을 포함하는 그래프 G^영어가 존재한다. 가능한 G^영어의 가장 작은 꼭짓점 수는 '''유도된 램지 수'''이다.^[31]^[32]^[33]

때로는 문제의 비대칭 버전도 고려한다. 를 빨간색 또는 파란색만 사용하여 G^영어의 변을 색칠할 때 빨간색 유도 부분 그래프 X^영어 또는 파란색 유도 부분 그래프 Y^영어를 포함하는 그래프 G^영어의 가능한 가장 작은 꼭짓점 수로 정의한다.

6. 2. 역사 및 경계

에르되시, 허이날, 포사, Deuber, 뢰들은 1970년대에 독립적으로 유도 램지 수가 존재함을 증명하였다.^[31]^[32]^[33] 하지만 최초 증명은 유도 램지 수에 대한 매우 큰 경계(예: 2의 탑)를 제시했다.

1974년 에르되시는 k개의 정점을 갖는 모든 그래프 H에 대해 를 만족하는 상수 c가 존재한다고 추측했다.^[34] 그러나 이 추측은 아직 미해결 상태이다.

1998년 고하야카와, Prömel, 뢰들은 라는, 2의 거듭제곱에 가까운 경계를 처음으로 증명했다.

2010년 콘론, 폭스, 수다코프는 경계를 로 개선했으며, 이는 현재까지 알려진 일반적인 유도 램지 수에 대한 가장 좋은 상한이다.^[38]

현재, 라는 에르되시의 추측은 극단 그래프 이론에서 중요한 미해결 문제 중 하나이다. 하한의 경우, 유도 램지 수가 적어도 해당 램지 수여야 한다는 사실 외에는 알려진 바가 많지 않다.

6. 3. 특수한 경우

H^영어가 k개의 정점을 갖는 사이클, 경로 또는 별이면, r는 k에 대해 선형으로 증가한다.

7. 확장

램지 정리는 무한 그래프, 하이퍼그래프, 유향 그래프 등으로 확장될 수 있다.

무한 그래프: 가산 무한 집합과 관련된 무한 램지 정리가 있으며, 에르되스-더쉬닉-밀러 정리에 따르면 모든 무한 그래프는 가산 무한 독립 집합 또는 원래 그래프와 동일한 기수를 가진 무한 클릭을 포함한다.^[45]
하이퍼그래프: 램지 정리는 "변"이 여러 개의 정점 집합인 하이퍼그래프로 확장될 수 있다. 예를 들어, 3-하이퍼그래프에서 램지 수 R(3,4;3) = 13 이라는 사실이 맥케이와 Stanisław Radziszowski|스타니스와프 라지슈토프스키^영어에 의해 밝혀졌다.^[47]
유향 그래프: 에르되시와 Moser|모저^영어는 유향 그래프에 대한 램지 수를 정의했다.^[49] 이는 사이클이 없는 부분 토너먼트를 포함하는 최소 노드 수를 나타낸다.

7. 1. 무한 그래프

무한 램지 정리(infinite Ramsey theorem^영어)는 유한 램지 정리를 확장한 것이다. 이 정리는 다음과 같이 표현된다.

임의의 양의 정수 m, c와 임의의 가산 무한 집합 S에 대해, S의 m-원소 부분집합([math]\textstyle\binom Sm[/math])을 c개의 부분집합([math]\textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c[/math])으로 분할할 때, [math]\textstyle\binom Tm\subseteq E_i[/math]를 만족하는 무한 부분집합 T⊆S와 i∈{1,...,c}가 존재한다.

이는 [math]\aleph_0=R(\aleph_0,\aleph_0,\dots,\aleph_0;m,c)[/math]로 표현할 수 있다.^[44]

무한 그래프에 대한 램지 정리는 다음과 같이 집합론적 용어로 표현된다.^[44]

'''정리'''. X를 무한 집합이라 하고, [math]X^n[/math](크기가 n인 X의 부분집합)의 원소에 c개의 서로 다른 색을 칠한다. 그러면 X의 무한 부분집합 M이 존재하여 M의 크기 n인 모든 부분집합이 동일한 색을 가진다.

에르되스-더쉬닉-밀러 정리에 따르면, 모든 무한 그래프는 가산 무한 독립 집합 또는 원래 그래프와 동일한 기수를 가진 무한 클릭을 포함한다.^[45]

유한 램지 정리는 귀류법과 컴팩트성 논증을 통해 무한 램지 정리로부터 유도할 수 있다.^[46]

7. 2. 하이퍼그래프

램지 정리는 하이퍼그래프로 확장될 수도 있다. -하이퍼그래프는 "변"이 개의 정점 집합인 그래프이다. 일반적인 그래프에서 변은 2개의 정점 집합이다. 하이퍼그래프에 대한 램지 정리의 전체적인 내용은, 임의의 정수 과 및 임의의 정수 에 대해, 완전 -하이퍼그래프의 하이퍼변을 개의 서로 다른 색으로 칠했을 때, 1에서 사이의 어떤 에 대해 색 의 모든 하이퍼변을 가진 차수 의 완전 부분 -하이퍼그래프를 포함하도록 하는 정수 이 존재한다는 것이다. 이 정리는 일반적으로 그래프의 '하이퍼성'인 에 대한 귀납법으로 증명된다. 증명의 기본 사례는 로, 이는 위의 정리와 정확히 같다.

인 경우, 우리는 한 가지 비자명한 램지 수의 정확한 값을 알고 있는데, 이는 이다. 이 사실은 1991년 브렌던 맥케이(Brendan McKay)와 스타니스와프 라지슈토프스키(Stanisław Radziszowski)에 의해 밝혀졌다.^[47] 또한, 우리는 ,^[48] 및 를 가지고 있다.^[48]

7. 3. 유향 그래프

Ramsey^영어 수와 유사하게, 유향 그래프에 대한 Ramsey^영어 수도 정의할 수 있다. 이는 에르되시와 Moser|모저^영어에 의해 처음 소개되었다.^[49] 을, 단일 방향의 호(또는 "토너먼트")를 가진 개의 노드를 가진 완전 그래프가 사이클이 없는(또는 "추이적인") 개의 노드 부분 토너먼트를 포함하도록 하는 최소의 수 라고 하자.

이것은 라고 불리는 것의 유향 그래프 유사체이며, 개의 노드를 가진 완전 무향 그래프의 변을 2-채색하면, 개의 노드에 대한 단색 완전 그래프를 포함하도록 하는 최소의 수 이다. 유향 그래프에서 두 가지 가능한 호의 '색상'은 호의 두 '방향'이며, '단색'의 유사체는 '모든 호-화살표가 같은 방향을 가리키는' 경우, 즉 '사이클이 없는' 경우이다.

, , , , , , , 그리고 이다.^[49]^[50]

8. 역사

프랭크 램지가 1930년에 1차 논리의 특정 부분 집합의 결정 문제를 증명하는 도중 보조정리로서 증명하였다.^[57] 이는 훗날 에르되시 팔 등에 의하여 발전된 램지 이론의 시초로 여겨진다.

램지 정리에서 나오는 수 (그리고 두 가지 색상 이상으로의 확장)는 램지 수로 알려져 있다. 램지 수 는 파티 문제에 대한 해답을 제공하는데, 이 문제는 적어도 명이 서로를 알거나 적어도 명이 서로를 모르게 하기 위해 초대해야 하는 최소 손님 수를 묻는다. 그래프 이론의 언어로, 램지 수는 순서 의 모든 무방향 단순 그래프가 의 크기를 가진 클릭 또는 의 크기를 가진 독립 집합을 포함하도록 하는 최소 정점 수 이다. 램지 정리는 모든 과 에 대해 그러한 수가 존재한다고 명시한다.

에 대한 상한은 정리의 증명에서 추출할 수 있으며, 다른 논증은 하한을 제공한다. (첫 번째 지수 하한은 폴 에르되시가 확률적 방법을 사용하여 얻었다.) 그러나 가장 조밀한 하한과 가장 조밀한 상한 사이에는 엄청난 격차가 있다. 또한 의 정확한 값을 알고 있는 과 의 수는 매우 적다.

에 대한 하한 을 계산하려면 일반적으로 파란색/빨간색으로 그래프 를 채색하여 파란색 부분 그래프와 빨간색 부분 그래프가 없도록 해야 한다. 이러한 반례를 "램지 그래프"라고 한다. 브렌던 맥케이는 알려진 램지 그래프 목록을 유지한다.^[3] 상한을 설정하는 것은 종종 훨씬 더 어렵다. 반례가 없음을 확인하기 위해 가능한 모든 채색을 확인하거나, 그것의 부재에 대한 수학적 논증을 제시해야 한다.

램지수의 성질에 관해서는, 특히 ''r''=''s''=2로 했을 때의 램지수 에 대해 많은 결과가 알려져 있으며, 다음의 결과 및 예시가 알려져 있다.

''R'' (''k'' , ''l'' )≤ ''R'' (''k'' -1, ''l'' )+''R'' (''k'' , ''l'' -1).
''R'' (''k'' , ''k'' )≤ 4''R'' (''k'' , ''k'' -2)+2.

램지수가 확정된 예는 다음 표와 같다.

램지수 / 램지수의 하계·상계
r\s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2		2	3	4	5	6	7	8	9	10
3			6	9	14	18	23	28	36	40–42
4				18	25^[54]	36–41	49–61	59^[55]–84	73–115	92–149
5					43–48	58–87	80–143	101–216	133–316	149^[55]–442
6						102–165	115^[55]–298	134^[55]–495	183–780	204–1171
7							205–540	217–1031	252–1713	292–2826
8								282–1870	329–3583	343–6090
9									565–6588	581–12677
10										798–23556

''r'' ≥ 3일 때 램지수가 확정된 것은 ''R''₃ (3, 3, 3)=17이 유일하게 알려져 있다.

이 외에도, 다음의 평가가 알려져 있다.

51≤ ''R''₄ (3, 3, 3, 3)≤ 62
162≤ ''R''₅ (3, 3, 3, 3, 3)≤ 307
538≤ ''R''₆ (3, 3, 3, 3, 3, 3)≤ 1838
1682≤ ''R''₇ (3, 3, 3, 3, 3, 3, 3)≤ 12861

이처럼 램지수에 관해서는 많은 성질이 알려져 있지만, 램지수가 확정된 경우는 매우 적고, 특정 파라미터에 대해서조차 램지수를 결정하는 것은 매우 어려운 문제이다.

9. 선택 공리와의 관계

역수학에서 무한 그래프에 대한 램지 정리(''n'' = 2인 경우)와 무한 멀티 그래프에 대한 램지 정리(''n'' ≥ 3인 경우) 사이에는 증명 강도에 상당한 차이가 있다. 램지 정리의 멀티 그래프 버전은 산술적 이해 공리와 강도가 동등하며, 이는 역수학의 5대 하위 시스템 중 하나인 2차 산술의 하위 시스템인 ACA₀에 속한다. 반면에, 데이비드 시타푼의 정리에 따르면, 램지 정리의 그래프 버전은 ACA₀보다 약하며, (시타푼의 결과와 다른 결과를 결합하여) 5대 하위 시스템 중 어느 곳에도 속하지 않는다.^[51] 그러나 ZF 위에서 그래프 버전은 고전적인 쾨니히의 보조정리를 함의하지만, 그 역은 성립하지 않는다.^[52] 왜냐하면 이 설정에서 쾨니히의 보조정리는 유한 집합으로부터의 가산 선택 공리와 동등하기 때문이다.^[53]

참조

_[1] 논문 Party problems and Ramsey theory http://www.austms.or[...]
_[2] 웹사이트 Party Acquaintances http://www.cut-the-k[...]
_[3] 웹사이트 Ramsey Graphs http://cs.anu.edu.au[...]
_[4] 서적 Ten Lectures on the Probabilistic Method https://archive.org/[...] SIAM
_[5] 웹사이트 2.6 Ramsey Theory from Mathematics Illuminated http://www.learner.o[...]
_[6] 논문 Quantum algorithms: an overview https://www.nature.c[...] 2016-01-01
_[7] 논문 Determining Ramsey numbers on a quantum computer
_[8] 논문 'R'(4,5) = 25 http://users.cecs.an[...] 1995-05-01
_[9] 논문 A lower bound for {{math| ''R''(5, 5)}} 1989-03-01
_[10] arXiv $R(5,5) \leq 46$ 2024-09-01
_[11] 논문 Subgraph Counting Identities and Ramsey Numbers http://cs.anu.edu.au[...]
_[12] 논문 Small Ramsey Numbers http://www.combinato[...] 2011-01-01
_[13] 웹사이트 DS1 https://www.cs.rit.e[...] 2023-08-17
_[14] arXiv $R(3,10) \leq 41$ 2023-12-31
_[15] 논문 New Lower Bounds for 28 Classical Ramsey Numbers http://www.combinato[...]
_[16] arXiv $R(5,5) \leq 46$ 2024-09-01
_[17] arXiv A Lower Bound for R(5,6) 2023-10-26
_[18] arXiv An exponential improvement for diagonal Ramsey
_[19] 웹사이트 A Very Big Small Leap Forward in Graph Theory https://www.quantama[...] 2023-05-02
_[20] 논문 A note on Ramsey numbers 1980-11-01
_[21] 논문 The Ramsey Number ''R''(3,''t'') has order of magnitude ''t''²/log ''t''
_[22] 웹사이트 The Triangle-Free Process and the Ramsey Number {{math|''R''(3,''k'')}} https://bookstore.am[...] 2023-06-27
_[23] 논문 Dynamic concentration of the triangle-free process https://doi.org/10.1[...] 2020-11-17
_[24] 논문 The early evolution of the H-free process https://doi.org/10.1[...] 2010-08-01
_[25] 논문 The asymptotics of r(4,t) 2024-03-05
_[26] 웹사이트 Mathematicians Discover Novel Way to Predict Structure in Graphs https://www.quantama[...] 2023-06-22
_[27] 간행물 Problems and Results on Graphs and Hypergraphs: Similarities and Differences https://doi.org/10.1[...] Springer 2023-06-27
_[28] 웹사이트 Erdős Problems https://www.erdospro[...] 2023-07-12
_[29] 간행물 A SAT+ Computer Algebra System Verification of the Ramsey Problem R(3,8) (Student Abstract) 2024-01-01
_[30] 논문 A formal proof of R(4,5)=25 2024-01-01
_[31] 학회자료 Strong embeddings of graphs into colored graphs North-Holland, Amsterdam/London 1975-01-01
_[32] 학회자료 A generalization of Ramsey's theorem North-Holland, Amsterdam/London 1975-01-01
_[33] Master's thesis The dimension of a graph and generalized Ramsey theorems Charles University 1973-01-01
_[34] 학회자료 Problems and results on finite and infinite graphs Academia, Prague 1975-01-01
_[35] 논문 On some problems in graph theory, combinatorial analysis and combinatorial number theory https://users.renyi.[...] 1984-01-01
_[36] 저널 Induced Ramsey Numbers https://www.cs.umd.e[...] 1998
_[37] 저널 Induced Ramsey-type theorems 2008
_[38] 저널 On two problems in graph Ramsey theory 2012
_[39] 서적 Mathematics of Ramsey Theory Springer, Berlin, Heidelberg 1990
_[40] 저널 On induced Ramsey numbers for graphs with bounded maximum degree 1996-03-01
_[41] 저널 Extremal results in sparse pseudorandom graphs 2014-05-01
_[42] 저널 Density theorems for bipartite graphs and related Ramsey-type results
_[43] 서적 A Journey Through Discrete Mathematics Springer, Cham 2017
_[44] 웹사이트 Ramsey Theory http://people.maths.[...]
_[45] 저널 Partially ordered sets
_[46] 서적 Graph Theory Springer-Verlag
_[47] 저널 The First Classical Ramsey Number for Hypergraphs is Computed 1991
_[48] 저널 A lower bound on the hypergraph Ramsey number R(4,5;3) 2018-12-31
_[49] 웹사이트 Partial Answer to Puzzle #27: A Ramsey-like quantity http://rangevoting.o[...] 2020-06-02
_[50] arXiv Tighter Bounds on Directed Ramsey Number R(7) 2020-11-01
_[51] 서적 Slicing the Truth World Scientific
_[52] 저널 Ramsey's theorem in the hierarchy of choice principles https://www.cambridg[...] 1977-09-01
_[53] 저널 Ramsey's theorem and König's Lemma https://link.springe[...] 2007-01-01
_[54] 웹사이트 Ramsey Graphs http://cs.anu.edu.au[...] 2019-03-02
_[55] 저널 New Lower Bounds for 28 Classical Ramsey Numbers http://www.combinato[...]
_[56] 저널 Small Ramsey numbers http://www.combinato[...] 2014-01-12
_[57] 저널 On a problem of formal logic

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com