Математик-любитель совершил прорыв в решении многолетней проблемы в сфере графов

24 сентября 2018

Проблемы графов не имеют срока давности. Теория графов используется в компьютерных сетях, применяется в геоинформационных системах, при маршрутизации сигналов в цифровых сетях и т.д. Даже социальные сети – это воплощение графов, где каждый пользователь (или его страничка) — это вершина графа, а подписчики и друзья – его ребра. Именно поэтому нас заинтересовала статья о решении одной из проблем в области графов, перевод которой мы вам предлагаем.

Автор: Эвелин Ламб (Evelyn Lamb)

Источник: https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/

---

Геронтолог вписал свое имя в историю математики, добившись значительного прогресса в решении проблемы хроматического числа плоскости за более чем 60 лет.

В 1950 году Эдвард Нельсон (Edward Nelson), на тот момент студент Чикагского университета, задал обманчиво простой вопрос, над которым математики ломали головы десятилетиями. «Представьте», — сказал Эдвард, — «граф – набор точек, связанных линиями. Убедитесь, что все линии одинаковой длины, а сам граф лежит на плоскости. Затем, раскрасьте все точки так, чтобы любые две соединенные точки имели разные цвета. Каким наименьшим количеством цветов можно раскрасить любой такой граф, даже состоящий из бесконечного количества вершин?»

Эта проблема известна как проблема Нельсона-Хадвигера и заключается в поиске хроматического числа плоскости. Она привлекла множество математиков, включая знаменитого Пала Эрдёша (Paul Erdős). Ученые быстро сузили набор возможных решений и пришли к тому, что бесконечный граф можно раскрасить не менее чем четырьмя и не более чем семью цветами. Другие сумели доказать несколько промежуточных результатов за последующие десятилетия, однако никому не удалось изменить эти границы.

А совсем недавно Обри де Грей (Aubrey de Grey), биолог, известный своими утверждениями о том, что люди, живущие сегодня, смогут прожить до 1000 лет, опубликовал статью под названием «Хроматическое число плоскости равно как минимум 5» на сайте предварительных научных публикаций arxiv.org. В этой статье он описывает структуру графа единичных расстояний, который нельзя раскрасить четырьмя цветами. Его открытие является первым значительным прорывом в решении проблемы, начиная с того момента, как она была поставлена. «Мне невероятно повезло», — утверждает де Грей. — «Не каждый день кто-то находит решение задачи, которой более 60 лет».

Де Грей не похож на математика-новатора. Он является сооснователем и главным научным сотрудником организации, занимающейся разработкой технологий для «предотвращения негативных эффектов старения». Он наткнулся на хроматическое число плоскости, когда играл в настольную игру. Много лет назад, де Грей играл на турнирах по Отелло (также известной под названием Реверси), где познакомился с математиками, таким же энтузиастами этой игры. Они, в свою очередь, познакомили де Грея с теорией графов, после чего тот периодически возвращался к ней. «Иногда, когда мне нужно отдохнуть от своей работы, я думаю о математике», — сказал де Грей. — «На прошлое рождество мне подвернулся такой шанс». Математик-любитель, который добивается значительного прогресса над старыми и нерешенными задачами, явление редкое, но в этом нет ничего необычного. В 1970-х Марджори Райс (Marjorie Rice), домохозяйка без математического образования, наткнулась на статью в журнале Scientific American, в которой говорилось о пятигранниках, покрывающих плоскость. Спустя какое-то время, она добавила четыре новых пятигранника в этот список. Джил Калай (Gil Kalai), математик из Еврейского университета в Иерусалиме, говорит, что приятно видеть, когда непрофессиональный математик совершает крупный прорыв. «Это вносит вклад в многогранный математический опыт», — утверждает Джил.

Обри де Грей построил первый граф единичных расстояний, который требует не менее пяти цветов. Предоставлено: Обри де Грей / Научно-исследовательский фонд SENS

Возможно, самая известная проблема раскрашивания графа – теорема четырех красок. Она утверждает, что любая карта может быть раскрашена при помощи четырех цветов таким образом, чтобы цвета соседних стран не совпадали. Размер и форма стран не играют роли, так что математики могут перенести эту проблему в мир графов, представив каждую страну в виде вершины графа, соединив ребрами те из них, которые имеют общие границы.

Люси Рединг-Икканда / Quanta Magazine

Проблема Нельсона-Хадвигера немного отличается от теоремы четырех красок. Вместо рассматривания конечного количества вершин (как, например, на карте), в ней рассматривается бесконечное количество вершин, по одной для каждой точки на плоскости. Две точки соединены ребром, если они находятся на единичном расстоянии. Чтобы найти нижнюю границу хроматического числа, достаточно создать граф с конечным количеством вершин, для раскрашивания которого потребуется определенное количество цветов. Именно это и сделал де Грей.

Де Грей построил свой граф при помощи веретена Мозера, названного так в честь математиков Лео и Вильяма Мозера. Эта конфигурация состоит из семи вершин и одиннадцати ребер и имеет хроматическое число равное четырем. С помощью тонкого процесса и минимального использования компьютера, де Грей совместил копии веретена Мозера и других небольших наборов точек в монстра с 20425 вершинами, которой нельзя раскрасить при помощи 4 цветов. Позже он смог уменьшить этот граф до 1581 вершин и при помощи компьютера проверил, что его нельзя раскрасить при помощи четырех цветов.

Граф де Грея с 1581 вершиной.
Елена Шмахало / Quanta Magazine; Источник: Обри де Грей

Открытие любого графа, для раскрашивания которого необходимо пять цветов крупное достижение, но математики хотели узнать, могут ли они найти граф меньшего размера, для которого также необходимо пять цветов. Возможно, если им удастся найти пятицветный граф меньшего размера, ученые продвинутся в решении проблемы Нельсона Хадвигера, что позволит доказать, что для раскрашивания графа, состоящего из всех точек плоскости необходимо ровно пять цветов (или шесть, или семь).

Де Грей представил эту проблему (поиска наименьшего графа, для раскрашивания которого необходимо пять цветов) Теренсу Тао (Terence Tao), математику из Калифорнийского университета, Лос-Анджелес, как потенциальную задачу для проекта Polymath. Polymath был основан около 10 лет назад, когда Тимоти Гауэрс (Timothy Gowers), математик из Кембриджского университета придумал, как использовать массовое сотрудничество математиков в интернете. Работа над проектами в Polymath ведется публично, а свой вклад может внести каждый. Недавно де Грей принял участие в совместном проекте Polymath, который привел к значительному прогрессу в проблеме чисел-близнецов.

Тао говорит, что не каждая проблема хорошо подходит для Polymath, но находка де Грея удовлетворяет основным условиям. Проблему легко понять и начать над ней работать, а также она имеет четкий индикатор успеха: уменьшение количества вершин графа, который нельзя раскрасить четырьмя цветами. Довольно быстро Дастин Миксон (Dustin Mixon), математик из университета штата Огайо, и его коллега Борис Алексеев (Boris Alexeev) нашли граф с 1577 вершинами. Позже Марейн Хеуле (Marijn Heule), специалист в сфере вычислительных систем Техасского университета, Остин, нашел граф с 874 вершинами. Некоторое время спустя он уменьшил это число до 826.

Эта работа побуждает математиков взглянуть на проблему Нельсона-Хадвигера еще раз. «Для такой проблемы конечное решение может потребовать использования невероятно сложных вычислений», — утверждает Гордон Ройл (Gordon Royle), математик из университета Западной Австралии. — «А может хватить и чьей-то изобретательности, которая поможет найти граф, для раскрашивания которого необходимо множество цветов».

Эта статья была повторно опубликована на Wired.com.

Теги: популярная математика, теория графов, теорема четырех красок, граф единичных расстояний