램지 이론: 두 판 사이의 차이

내용 삭제됨 내용 추가됨
편집 요약 없음
태그: m 모바일 웹
내용을 "'''램지 이론'''은 프랭크 램지가 창안한 수학의 분야이다. 대표적으로 램지의 정리 문제가 있다. "(으)로 바꿈
1번째 줄:
'''램지 이론'''은 [[프랭크 램지]]가 창안한 수학의 분야이다. 대표적으로 [[램지의 정리]] 문제가 있다.
램파랑으로 칠한다. 한 꼭짓점 v를 보면, 그 꼭짓점에는 5개의 변이 연결되어 있다. 비둘기집 원리에 의해, 적어도 그 중 3개는 같은 색이다. 그 색을 파랑이라고 가정 하고, 그 3개의 변에 연결된 꼭짓점을 각각 r, s, t라고 하자
 
[[분류:램지 이론| ]]
만약 변 (r, s), 변 (t, r), 변 (s, t) 중 어느 하나라도 파랑이면, v와 함께 파란색 삼각형(3개의 꼭짓점을 가지는 완전 그래프)이 생긴다. 만약 어느 하나도 파랑색이 아니면, (r, s), (t ,r), (s, t)는 모두 빨강색이므로 빨강색의 삼각형이 생긴다. 그러므로, 6개의 꼭짓점을 가지는 완전그래프 K6의 변을 두 가지 색으로 칠하는 경우, 동일한 색의 K3를 포함하게 된다. 즉, R(3,3) ≤ 6이다.
 
한편, K5를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, R(3,3) > 5 이다. 결론적으로 R(3,3)=6램지의 정리에 따르면 다음 조건을 만족시키는 양의 정수 {\displaystyle R(n_{1},\dots ,n_{m};c,m)} {\displaystyle R(n_{1},\dots ,n_{m};c,m)}가 존재한다.
 
임의의 집합 {\displaystyle S} S 및 {\displaystyle \textstyle {\binom {S}{m}}} {\displaystyle \textstyle {\binom {S}{m}}}의 {\displaystyle c} c개 조각으로의 분할 {\displaystyle \textstyle {\binom {S}{m}}=E_{1}\sqcup \cdots \sqcup E_{c}} {\displaystyle \textstyle {\binom {S}{m}}=E_{1}\sqcup \cdots \sqcup E_{c}}에 대하여, 만약 {\displaystyle |S|\geq R(n_{1},\dots ,n_{c};c,m)} {\displaystyle |S|\geq R(n_{1},\dots ,n_{c};c,m)}라면, 다음 조건을 만족시키는 부분 집합 {\displaystyle T\subseteq S} {\displaystyle T\subseteq S}와 {\displaystyle i\in \{1,\dots ,c\}} {\displaystyle i\in \{1,\dots ,c\}}가 존재한다.
{\displaystyle |T|\geq n_{i}} {\displaystyle |T|\geq n_{i}}이며, {\displaystyle \textstyle {\binom {T}{m}}\subseteq E_{i}} {\displaystyle \textstyle {\binom {T}{m}}\subseteq E_{i}}이다.
이는 그래프 이론으로 해석할 수 있다. {\displaystyle m} m-초그래프(영어: hypergraph)는 꼭짓점과 {\displaystyle m} m-초변(영어: hyperedge)들로 구성된 조합론적 구조이며, 여기서 {\displaystyle m} m-초변은 {\displaystyle m} m개의 꼭짓점들로 구성된 집합이다. (즉, 2-초그래프는 그래프와 같은 개념이다.) 임의의 꼭짓점 집합 {\displaystyle S} S에 대하여, 초변 집합이 {\displaystyle \textstyle {\binom {S}{m}}} {\displaystyle \textstyle {\binom {S}{m}}}인 초그래프를 완전 {\displaystyle m} m-초그래프라고 하자. (즉, 완전 2-초그래프는 완전 그래프이다.) 이 경우, {\displaystyle \textstyle {\binom {S}{m}}} {\displaystyle \textstyle {\binom {S}{m}}}의 {\displaystyle c} c개 조각으로의 분할은 완전 초그래프의 초변들을 {\displaystyle c} c개의 색깔로 색칠하는 것과 같다. 이 경우, 위와 같은 성질을 갖는 {\displaystyle T} T는 동색의 클릭이라고 한다.
 
따라서, 램지 정리에 따르면, {\displaystyle R(n_{1},\dots ,n_{c};c,m)} {\displaystyle R(n_{1},\dots ,n_{c};c,m)}개 이상의 꼭짓점을 가진 완전 {\displaystyle m} m-초그래프의 초변들을 {\displaystyle c} c개의 색깔로 색칠한다면, 1번 색깔의, 크기 {\displaystyle n_{1}} n_{1}의 클릭을 가지거나, 아니면 2번 색깔의, 크기 {\displaystyle n_{2}} n_{2}의 클릭을 가지거나, …… 또는 {\displaystyle c} c번 색깔의, 크기 {\displaystyle n_{c}} {\displaystyle n_{c}}의 클릭을 갖는다.
 
램지 정리에 따라 존재하는 양의 정수 {\displaystyle R(n_{1},\dots ,n_{c};c,m)} {\displaystyle R(n_{1},\dots ,n_{c};c,m)}을 램지 수(영어: Ramsey number)라고 한다. 일반적으로, {\displaystyle c=m=2} {\displaystyle c=m=2}일 경우 {\displaystyle R(r,s;2,2)=R(r,s)} {\displaystyle R(r,s;2,2)=R(r,s)}로 표기한다.
 
역사 편집