대칭 램지 수의 실험적 증명 = Experimental Proof for Symmetric Ramsey Numbers

국문 초록 (Abstract)

본 논문은 램지 수에 대해 해결하지 못한 43 ≤ R(5,5) ≤ 49와 102 ≤ R(6,6) ≤ 165의 문제를 해결하였다. Kn 완전 그래프의 램지 수 R(s,t)는 임의의 정점 ν의 n-1개 부속 간선수가 (n-1)/2=R과 (n-1)/2=B의 2가지색으로 정확히 양분된다. 따라서 임의의 정점 ν로부터 거리 개념을 적용하여 {KL, ν}의 (n-1)/2=R, {ν, KR}의 (n-1)/2=B색이 되도록 Kn=KL+ν+KR분할 그래프를 형성하였다. 이로부터 KL이 Ks-1의 R색을 형성하면 Ks를 얻을 수 있다. KR이 Kt-1의 B색을 형성하면 Kt를 얻는다. KL과 KR의 최대 거리는 짝수와 모든 정점의 부속 간선 수는 동일하다는 필요충분조건을 만족시키는 R (s,t)=Kn을 구하였다. 결국, R(5,5)=43과 R(6,6)=91 을 증명하였다.

다국어 초록 (Multilingual Abstract)

This paper offers solutions to unresolved 43 ≤ R(5,5) ≤ 49 and 102 ≤ R(6,6) ≤ 165 problems of Ramsey’s number. The Ramsey’s number R(s,t) of a complete graph Kn dictates that n-1 number of incidental edges of a arbitrary vertex ν is dichotomized into two colors: (n-1)/2=R and (n-1)/2=B. Therefore, if one introduces the concept of distance to the vertex ν, one may construct a partite graph Kn=KL+ν+KR, to satisfy (n-1)/2=R of {KL, ν} and (n-1)/2=B of {ν, KR}. Subsequently, given that KL forms the color R of Ks-1, Ks is attainable. Likewise, given that KR forms the color B of Kt-1, Kt is obtained. By following the above-mentioned steps, R(s,t)=Kn was obtained, satisfying necessary and sufficient conditions where, for KL and KR, the maximum distance should be even and incidental edges of all vertices should be equal are satisfied. This paper accordingly proves R(5,5)=43 and R(6,6)=91.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 관련 연구와 연구 배경
• Ⅲ. 대칭 램지 수 R(s,t) 증명 방법
• Ⅳ. 실험 및 결과 분석
• Ⅴ. 결론
• REFERENCES

참고문헌 (Reference)

1 Wikipedia, "Theorem on Friends and Strangers" Wikimedia Foundation Inc.

2 B. D. McKay, "Subgraph Counting Identities and Ramsey Numbers" 69 (69): 193-209, 1997

3 C. J. Kunkel, "RamseyNumbers: Improving the Bounds of R(5,5)" 2003

4 Wikipedia, "Ramsey's Theorem" Wikimedia Foundation Inc.

5 E. W. Weisstein, "Ramsey's Theorem" MathWorld, Wolfram Research, Inc.

6 Wikipedia, "Ramsey Theory" Wikimedia Foundation Inc

7 G. E. W. Taylor, "Ramsey Theory" School of Mathematics, The University of Birmingham 2006

8 E. W. Weisstein, "Ramsey Number" MathWorld, Wolfram Research, Inc

9 Wikipedia, "Pigeonhole Principle" Wikimedia Foundation Inc.

10 F. P. Ramsey, "On a Problem of Formal Logic" 30 : 264-286, 1930

11 Math Explorers' Club, "Howto Play Ramsey Graph Games" Math Explorers' Club, Cornell Department of Mathematics 2004

12 J. A. Bondy, "Graduate Texts in Mathematics: Graph Theory" Springer-Verlag 2006

13 Z. Bian, "Experimental Determination of Ramsey Numbers" 111 (111): 1-6, 2013

14 X. Xiaodong, "Constructive Lower Bounds on Classical Multicolor Ramsey Numbers" 11 (11): 1-24, 2004

15 I. Leader, ""Friends and Strangers," Millenium Mathematics Project" University of Cambridge 2001