d라이브러리

1973년 미국의 수학자인 스테판 버어는 에르되시와 함께 램지 수 문제를 대상 사이의 관계를 점과 선으로 나타내 알아보는 그래프 문제로 바꿔 생각했습니다. 사람은 꼭짓점에, 서로 알거나 모르는 관계를 각각 다른 색으로 칠한 선에 대응한 것이죠. 그래프에서 램지 수 R(3,3)을 찾는 것은 그래프에서 각 점을 서로 알거나 모름을 나타내는 두 가지 색으로 연결했을 때 같은 색의 변으로 연결된 삼각형이 존재하는지를 알아보는 것과 같습니다.

이제 R(3,3)을 ‘6개의 꼭짓점을 가지는 완전그래프의 각 선을 빨강과 파랑 두 색으로 칠하는’ 그래프 문제로 바꿔 풀어보겠습니다. 여기서 ‘완전그래프’란 그래프 중에서도 모든 점이 서로 연결된 그래프를 말합니다. 만약 빨간 삼각형 혹은 파란 삼각형이 만들어지지 않도록 아무리 노력해도 반드시 같은 색의 선으로 이뤄진 삼각형이 나온다면 R(3,3)은 6보다 작거나 같을 겁니다.

한 꼭짓점에 연결된 5개의 변 중 5개 모두를 빨강으로 칠하면 파랑으로 칠한 변은 0개가 되고, 4개가 빨강이면 파랑은 1개, 3개가 빨강이면 파랑은 2개가 됩니다. 2개가 빨강이면 파랑은 3개가 되고, 1개가 빨강이면 파랑은 4개가 되니 빨강과 파랑을 어떻게 분배하든 항상 같은 색으로 칠한 삼각형이 존재합니다. 파랑이 3개 이상인 경우를 자세히 알아봅시다.

한 점 a에서 각각 b, c, d로 그은 선분에 모두 파랑을 칠할 때 bc, cd, bd 중 하나라도 파랑이면 그림①처럼 파란 삼각형이 존재합니다. 파란 삼각형을 만들지 않으려고 세 선을 모두 빨강으로 칠하면 그림②처럼 빨간 삼각형 bcd가 존재하게 돼 반드시 한 가지 색으로 이뤄진 삼각형이 존재하죠. a에서 e를 더 잇거나 e, f를 모두 이어도 항상 삼각형이 만들어집니다. 즉, 꼭짓점이 6개일 때 한 가지 색의 변으로 이뤄진 삼각형이 반드시 생깁니다.

하지만 꼭짓점이 5개인 경우에는 같은 색으로만 이뤄진 삼각형이 존재하지 않는 경우가 있습니다. 그림③처럼 바로 옆의 꼭짓점끼리 같은 색으로 연결해 오각형을 만들고 다른 색으로 나머지 변을 칠하면 같은 색으로 이뤄진 삼각형이 생기지 않습니다. 즉 R(3,3)＞5이며 R(3,3)≤6이므로 R(3,3)=6입니다.

서로 아는 관계 또는 모르는 관계 r, s명이 있도록 하는 R(r, s)=N에서 그래프로 N을 찾는 방법도 마찬가지입니다. 우선 꼭짓점의 개수가 N개인 완전그래프를 그리고 변을 각각 다른 색으로 칠할 때, 크기가 k이고 그 사이의 변이 모두 같은 색으로 칠해진 부분 완전그래프가 존재하지 않도록 칠해야 합니다. 부분 완전그래프*가 존재하지 않는다면 램지 수는 N보다 크고, 존재하면 램지 수는 N보다 작거나 같은 수임을 알 수 있습니다.

용어정리

* 부분 완전그래프 : 어떤 그래프의 꼭짓점과 변 가운데 일부로 이뤄진 그래프에서 그 그래프가 완전그래프가 되는 경우