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