그래프 이론에서, 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일
