Они позволяют по-новому подойти к теореме о четырех красках, согласно которой любую карту можно раскрасить в четыре цвета, и открывают возможности для новых расчетов в комбинаторике, криптографии и теории кодирования. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в The Electronic Journal of Combinatorics.
Математики используют понятие «матроид» для описания свойства независимости для самых разных сущностей — от геометрических векторов до телекоммуникационных сетей. Ключевой числовой характеристикой матроида служит его характеристический многочлен, который сворачивает большой объем информации о количестве независимых подмножеств в одну компактную формулу (кодирует) и помогает, например, доказать теорему о четырех красках. Суть теоремы заключается в том, что если взять любую географическую карту — с любым количеством стран и границами между ними любой формы, то хватит всего четырех красок, чтобы раскрасить все страны так, чтобы соседние (имеющие общий участок границы, а не просто касающиеся в одной точке) были разного цвета.
Решение этой абстрактной математической задачи имеет практические аналоги. Например, можно представить, что каждый экзамен в университете — это вершина математического графа, а ребра соединяют те экзамены, которые нельзя проводить одновременно (например, на них должен присутствовать один и тот же студент). Раскрасить вершины графа в разные цвета — значит распределить экзамены по временным слотам так, чтобы конфликтующие не попали в один. Число использованных цветов покажет, сколько всего слотов потребуется.
Известное сейчас доказательство теоремы о четырех красках требует сложного компьютерного перебора тысяч возможных конфигураций. Это привело к тому, что часть математиков считают теорему о четырех красках топологической диковинкой с ужасным доказательством. Знаменитый физик и математик Роджер Пенроуз придумал красивый геометрический метод подсчета количества способов раскраски любой карты в четыре цвета с помощью так называемого многочлена Пенроуза. Его исключительные свойства указывают, что мы на самом деле не поняли истинного смысла теоремы о четырех красках — и, похоже, она является фокусной точкой топологии плоскости.
Математик из Казанского (Приволжского) федерального университета (Казань) разработал еще один подход к решению этой проблемы. Он нашел точные аналитические выражения для характеристического многочлена регулярных матроидов, используя идею «альфа-представления» из квантовой физики и свойства конечных полей, а затем применил тот же способ для подсчета количества раскрасок в четыре цвета произвольных графов. Новая формула позволяет искать алгебраические причины того, почему некоторые графы нельзя раскрасить в четыре цвета. Такой подход дает аргумент в пользу важности теоремы четырех красок не только с топологической, но и с алгебраической точки зрения.
«Альфа-представление — это метод из квантовой теории поля, который был введен более 70 лет назад для расчетов в квантовой электродинамике и хромодинамике. Мы неожиданно применили ту же технику к совершенно другим объектам математики. В результате нам удалось получить точные аналитические формулы для количества способов раскраски в четыре цвета в виде сумм некоторых дробей разных знаков, которые после сложения дают натуральное число. Это показывает, что глубокие идеи квантовой физики могут работать в комбинаторике, и открывает новые возможности для приложений. В дальнейшем мы хотели бы использовать этот подход для поиска другого доказательства теоремы четырех красок»,— заключает руководитель проекта, поддержанного грантом РНФ, Эдуард Лернер, кандидат физико-математических наук, доцент кафедры математической статистики института математики и механики имени Н. И. Лобачевского Казанского федерального университета.
