평면지도에서 이웃한 지역은 서로 다른 색으로 칠할 때 4색이면 충분하다는 ‘4색 정리’를 들어보셨나요? 4색 정리처럼 평면지도에서 각 지역을 적당한 조건을 만족하도록 잘 색칠하는 문제는 많이 연구되는 주제입니다. 그런데 최근 평면지도에서 어느 지역에서 출발해도 각 지역을 많아야 한 번만 들르도록 아무렇게나 짜서 돌아다녀도 만나는 색의 패턴이 연달아 나타나지 않도록 색을 칠하려고 할 때 몇 색이면 되는지 밝힌 연구가 나왔습니다.
숫자 1, 2, 3을 이용해 긴 수열을 만들 때 똑같은 숫자열이 연달아 반복되지 않게 만들 수 있을까요? 예를 들어 12312123에는 ‘12’ 다음에 이어서 ‘12’가 나오니 반복인 부분이 있습니다. 하지만 123132123213에는 그런 반복이 없습니다. 그렇다면 1, 2, 3만을 이용해 반복 없이 얼마나 길게 만들 수 있을까요?
숫자 1, 2만 가지고는 절대 불가능합니다. 11, 22를 쓸 수 없으니 1 다음에는 무조건 2가 와야 하고 2 다음에는 무조건 1이 와야 합니다. 그럼 1212가 반드시 생겨서 ‘12’가 반복됩니다.
하지만 1, 2, 3을 이용하면 반복 없이 원하는 만큼 아주 길게 만들 수 있습니다. 1906년 노르웨이의 수학자 악셀 투에는 반복이 없는 짧은 수열에서 숫자 1, 2, 3을 오른쪽 투에의 치환 규칙대로 서로 다른 숫자열로 치환하면 전보다 수열의 길이는 길어지지만, 여전히 반복이 없는 수열이 된다는 것을 증명했습니다.
예를 들어 수열 123에 투에의 치환 규칙을 적용하면 123121312321323132이 됩니다. 여기에 있는 모든 1, 2, 3을 다시 치환하면 123121312321323132123121312321231213231321231213123213231321312321231213231321312321323132123121323132131232라는 수열이 만들어집니다. 신기하게도 이런 식으로 계속 반복해 치환해도 숫자열이 연달아 반복되는 부분은 하나도 없습니다.
반복 없이 그래프 색칠하기
수학자들은 이 문제를 여러 가지 방식으로 바꿔 생각했습니다. 그중 하나는 문제를 그래프로 확장한 겁니다. 그래프는 지하철 노선도처럼 유한개의 꼭짓점과 두 꼭짓점을 잇는 선으로 이뤄진 수학적 대상을 일컫는데, 어느 두 꼭짓점이 선 하나로 연결돼 있으면 그 두 꼭짓점은 이웃한다고 표현합니다. 특히 어떤 두 선도 교차하지 않게 그릴 수 있다면 이 그래프를 ‘평면 그래프’라 하지요.
선으로 연결된 이웃한 꼭짓점을 가장 적은 색을 써서 서로 다른 색으로 칠하는 ‘4색 정리’는 평면 그래프 색칠 문제의 대표 난제였습니다. 1976년 두 명의 미국 수학자 케니스 아펠과 볼프강 하켄이 4가지 색이면 어떤 평면 그래프도 이웃한 꼭짓점이 다른 색이 되도록 칠할 수 있다고 밝혀 문제가 해결됐지요.
투에의 연구를 그래프 문제로 확장하기 위해 연결된 꼭짓점만 서로 다른 색으로 칠하는 보통의 그래프 색칠 문제보다 훨씬 복잡한 경우를 생각해봅시다. 우선 꼭짓점을 1번 색, 2번 색, 3번 색처럼 여러 종류의 색으로 칠했다고 가정합시다. 그리고 적당한 꼭짓점에서 출발해 각각의 꼭짓점을 많아야 한 번만 지나는 경로 중 아무거나 하나를 뽑습니다. 이렇게 뽑은 어떤 경로도 따라가면서 만나게 되는 색깔을 수열로 나타냈을 때 어떤 구간도 숫자열이 반복되지 않게 색을 칠할 수 있을까요? 만약 그렇게 색을 칠할 수 있다면 이를 ‘반복 없는 색칠’이라고 부릅시다.
반복 없는 색칠이 있다면 연결된 꼭짓점은 다른 색이 될 수밖에 없습니다. 연결된 두 꼭짓점의 색이 같을 경우 그 선으로 가는 경로는 수열에서 같은 수가 반복되기 때문이죠. 따라서 반복 없는 색칠을 하는데 필요한 색의 수는 보통의 그래프 색칠보다 같거나 많아야 합니다. 물론 모든 꼭짓점에 서로 다른 색을 준다면 항상 그런 색칠을 하는 것이 가능합니다. 하지만 수학자들은 최대한 색을 적게 쓰는 데 관심을 가졌습니다.
그렇다면 평면 그래프에서 각각의 꼭짓점을 많아야 한 번만 지나도록 이웃한 꼭짓점으로 이동할 때 어떤 경로도 색이 반복되지 않게 100만 개 이하의 색만 써서 칠할 수 있을까요?
몇몇 특수한 경우에 대해서는 가능합니다. 예를 들어 평면 그래프 중에서도 모든 꼭짓점이 어떤 한 면과 동시에 만날 때는 12색만 이용해 항상 반복 없게 색칠할 수 있습니다. 하지만 일반적인 평면 그래프에서는 색깔 수가 10의 100승 개라도 항상 반복 없는 색칠이 가능한지 알지 못했습니다. 이 질문은 2002년 노가 알론, 야로스와프 그리트추크, 마리우시 하우슈차크, 올리버 리오단이 함께 쓴 논문에 처음 등장하는데 10여 년 동안 아무도 전혀 감을 잡지 못했습니다.
뭉치면 풀린다!
그런데 최근 이 문제를 해결한 논문이 인터넷 논문 공개 사이트인 아카이브에 올라왔습니다. 2019년 4월 공개된 이 논문에 따르면 색의 수가 768개면, 모든 평면 그래프의 경로를 반복없는 색칠로 칠할 수 있습니다. 이 연구는 캐나다에 사는 비다 두이모비츠, 프랑스에 사는 루이 에스페레, 벨기에에 사는 그웨나엘 조렛, 폴란드에 사는 바르토시 발차크, 호주에 사는 데이비드 우드가 함께했습니다. 모두 다른 나라에 사는데 어떻게 함께 논문을 쓴 걸까요?
사실 이 연구의 마지막 작업은 2019년 4월 섬나라 바베이도스에서 열린 그래프이론 워크숍에서 이뤄졌습니다. 워크숍이 열리기 한 달 전쯤 이 문제를 푸는 데 매우 중요한 결과가 나왔고, 연구팀은 이 워크숍에서 그 결과를 이용해 이 문제의 증명법을 찾아낸 것이지요.
저도 이 워크숍에 참석했었는데요, 저녁 시간에 5명이 뭔가 하기에 대체 뭐 때문에 그러나 궁금했었는데 다음날 이런 결과를 얻었다고 발표하더군요. 실험실이 필요한 많은 과학 분야와는 달리, 수학 연구는 대부분 이렇게 연습장만 있으면 연구실을 떠나 어디서든지 함께 할 수 있습니다. 특히 각 분야 전문가들이 만나서 연구하면 어려운 문제도 서로의 지식을 합쳐 순식간에 해결하기도 합니다.
이 논문에서 증명한 768이라는 색의 수가 최솟값일 것 같지는 않습니다. 이 연구 역시 최솟값을 찾으려고 노력하지 않았습니다. 하지만 이제껏 백만 개든 1조 개든 어떤 상수 개의 색으로도 항상 반복 없이 색칠 가능하다는 걸 밝힌 적이 없었기 때문에 이 결과도 놀랍습니다.
지금까지 연구된 바로는 색이 적어도 11개가 필요한 평면 그래프가 있습니다. 즉 최솟값은 11에서 768까지 수 중 하나일 겁니다. 혹시 11색으로 반복 없는 색칠이 불가능한 평면 그래프를 찾았다면 꼭 알려주세요. 흥미로운 연구가 결과가 될 겁니다.
참고자료
비다 두이모비츠, 루이 에스페레, 그웨나엘 조렛, 바르토시 발차크, 데이비드 우드 ‘Planar graphs have bounded nonrepetitive chromatic number’, 노가 알론, 야로스와프 그리트추크, 마리우시 하우슈차크, 올리버 리오단 ‘Nonrepetitive colorings of graphs’
