R(5,5)의 upper bound가 하나 줄어들다

그래프 이론에서, n개의 점이 모두 연결되거나 m개의 점이 모두 연결되지 않은 subgraph가 항상 존재하는 vertex 개수의 최소값이 존재한다는 정리가 Ramsey’s theorem이다. 일전에 R(3,4)=9 의 증명을 설명한 적[1] 있으니 참고하기 바란다.

R(5,5)의 값은 아직도 알려지지 않았는데, 그 bound의 좁혀진 역사가 [2]에 설명이 잘 돼 있다. 43보다 크고[3] 49보다 작다[2]는 1997년까지의 결과가 여태까지 최신의 결과였다. wolfram mathworld[4]에는 49보다 작다는 결과의 증명이 1995년 논문[5]이라고 나와 있는데, 그 논문[5]을 대충 확인해보니 아무래도 mathworld를 작성한 사람이 착오를 한 것이 아닌가 싶다.

여하간 이 1997년 결과[2]가 여태까지 최신이라 지난 20년간 bound의 발전이 없었는데, Gil Kalai 선생의 블로그[6]를 보니 며칠 전에 upper bound가 48로 하나 줄었다[7]고 한다-_- 20년만의 진보인가 ㅋㅋㅋ

대충 보니 350,904 가지의 경우의 수로 나누어 센 모양인데, 일전에 454보다 큰 모든 자연수는 일곱개 이하의 세제곱수의 합으로 표현가능하다[8]는 이야기와 불리언 피타고라스 트리플 문제[9] 이야기도 했지만, 이제 이 동네는 컴퓨터 없으면 결과가 잘 안 나오는 것 같다. ㅋㅋㅋ

 


[1] 내 백과사전 R(3,4)=9 의 증명 2010년 9월 8일
[2] Brendan D. McKay and Stanis law P. Radziszowski. “Subgraph counting identities and Ramsey numbers”. Journal of Combinatorial Theory, Series B, 69(2):193–209, 1997
[3] Exoo, G. “A Lower Bound for R(5,5).” Journal of Graph Theory. 13, 97-98, 1989.
[4] http://mathworld.wolfram.com/RamseyNumber.html
[5] McKay, B. D. and Radziszowski, S. P. “R(4,5)=25.” Journal of Graph Theory 19, 309-322, 1995
[6] R(5,5) ≤ 48 by Gil Kalai
[7] Vigleik Angeltveit, Brendan D. McKay (2017) “R(5,5)≤48”, arXiv:1703.08768 [math.CO]
[8] 내 백과사전 454보다 큰 모든 자연수는 일곱개 이하의 세제곱수의 합으로 표현가능하다 2016년 1월 20일
[9] 내 백과사전 불리언 피타고라스 트리플 문제가 해결되었나? 2016년 5월 28일

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중