평면의 채색수

평면을 색 몇 개를 이용해 칠하되, 거리가 1인 어떤 두 점도 서로 다른 색이 되도록 칠하려고 할 때 필요한 색의 개수의 최솟값은?

Hadwiger-Nelson problem으로 알려진 조합기하 문제이다. 여기서 따지고 있는 필요한 색의 개수의 최솟값 는 평면의 채색수(chromatic number)라 불린다.

평면을 위 그림처럼 7개의 색을 가진 육각형들로 타일링함으로써, 7개의 색만으로 조건을 만족시키게 하는 것이 가능함을 보일 수 있다. 또한 위 그림에 있는 그래프의 한 변의 길이가 전부 1이라면, 위 그래프의 꼭지점들은 3개의 색으로 칠할 수 없다는 것을 확인할 수 있다. (이 그래프는 Moser spindle이라 부름) 따라서 이 둘을 종합하면 이 된다.

처음 Edword Nelson이 1950년 질문을 던진 이후로 이 의 값이 무엇인지는 아직도 오픈이다. 그러던 터에 얼마 전 생물학자가 임을 증명하는 페이퍼를 arXiv에 올렸다.[1] 그는 이를 위해 점의 개수가 1581개인 한 변의 길이가 1인 변들로 이루어진 그래프를 직접 건설해 이 그래프가 4개의 색으로 칠할 수 없음을 보였다.

페이퍼는 부담없이 읽기 쉽게 구성되어있다. Polymath16으로 이 그래프의 점 개수를 더 낮추는 폴리매스 프로젝트가 진행되었으며, 현재 553개의 점을 가진 그래프가 발견된 것들 중 최소인 듯함.[2]

트윗 타래를 정리. (2018/04/10)

https://t.co/unVXQCsvyJ Aubrey De Grey가 평면의 chromatic number가 4는 될 수 없음을 constructive하게 증명

— 유닼 (@udaqueness) April 10, 2018

References

[1] A. de Grey, “The chromatic number of the plane is at least 5” arXiv preprint arXiv: 1804.02385, 2018.

[2] M. Heule, “Computing Small Unit-Distance Graphs with Chromatic Number 5” arXiv preprint arXiv: 1805.12181, 2018.