Биолог взломал проблему, над которой математики бьются 68 лет

Любитель-математик Хадвигер-Нельсон вскрыл проблему, которая раздражает математиков с 1950 года.

Обри де Грей — биолог, который более известен тем, что берётся радикально расширить человеческую жизнь, и предсказал, что первый человек, которому суждено прожить 1000 лет, уже родился — опубликовал документ на сервере preprint arXiv, который сужает ответ на 68-летнюю проблему Хадвигера-Нельсона.

Математики знали годами, что проблема (которую мы рассмотрим через секунду) имеет ответ либо 4, 5, 6, либо 7. Де Грей в своей статье показал, что это определённо не 4. Остаются только 5, 6 или 7.

Возьмите холст и нарисуйте на нём кучу точек (называемых вершинами). Если какие-либо точки находятся на расстоянии 1 единицы друг от друга, проведите между ними линию. Математикам всё равно, если «единица» — сантиметр или километр. Это не имеет значения. Единица одинаковая между всеми связанными вершинами. Линии, соединяющие точки, называются «рёбрами». Математики называют это графом единичного расстояния. Это будет выглядеть примерно так:

Теперь пришло время раскрасить все точки.
Спросите себя: каково минимальное количество цветов краски вам потребуется, чтобы раскрасить на любом графике вершины таким образом, чтобы никакие две точки, разделяющие край, не имели одинакового цвета?
Диаграмма единичного расстояния не может быть окрашена всего тремя цветами, но четырьмя может. Вот хороший пример:

Придумать граф единичного расстояния, который нельзя покрасить четырьмя цветами, намного сложнее. Компьютеры не могут сделать это самостоятельно. Математики не справлялись с этим в течение 68 лет, пока Де Грей не придумал своё чудовище:

График Де Грея имеет 1 581 вершин. И они устроены таким образом, что вы не сможете разрисовть их четырьмя красками. Для работы необходимо не менее пяти.
Но это не значит, что пять — абсолютный минимум. Математики знают, что возможно, есть график, который потребует шесть цветов краски или даже семь. (Еще в 1950 году математик Джон Исбелл разработал стратегию, включающую семь цветов для решения любого графика).
Необходимый абсолютный минимум остаётся загадкой. Но благодаря Грею, мы знаем, что минимум больше четырёх.