Методы квантовой физики помогли найти новый подход к доказательству теоремы о четырех красках

Математик разработал новый способ расчета важной числовой характеристики для целого класса математических объектов — регулярных матроидов. Эти объекты описывают идею «независимости» параметров в самых разных системах и имеют приложения в областях от компьютерной лингвистики и криптографии до генетики и сетевых телекоммуникаций. Ученый соединил метод из квантовой физики и свойства необычных числовых математических структур — конечных полей Галуа — и получил точные формулы. Они позволяют по-новому подойти к теореме о четырех красках, согласно которой любую карту можно раскрасить в четыре цвета, и открывают возможности для новых расчетов в комбинаторике, криптографии и теории кодирования. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в The Electronic Journal of Combinatorics.

Математики используют понятие «матроид» для описания свойства независимости для самых разных сущностей — от геометрических векторов до телекоммуникационных сетей. Ключевой числовой характеристикой матроида служит его характеристический многочлен, который сворачивает большой объем информации о количестве независимых подмножеств в одну компактную формулу (кодирует) и помогает, например, доказать теорему о четырех красках. Суть теоремы заключается в том, что, если взять любую географическую карту — с любым количеством стран и границами между ними любой формы, — то хватит всего четырех красок, чтобы раскрасить все страны так, чтобы соседние (имеющие общий участок границы, а не просто касающиеся в одной точке) были разного цвета.

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