Аннотация результатов, полученных в 2024 году
1. Первая часть результатов касается условного потокового и хроматического многочленов. Количество правильных раскрасок с фиксированными красками некоторых вершин представлено (подобно формуле условной вероятности) в виде отношения двух обычных хроматических многочленов. Доказано, что это отношение тоже представляет собой многочлен, благодаря этому введено понятие условного хроматического многочлена. Доказано, что количество всюду ненулевых потоков в группе Z/mZ при фиксированных целочисленных внешних импульсах и достаточно больших m представляет собой многочлен от m, введено понятие потокового многочлена. Условный потоковый и условный хроматический многочлен для произвольного графа представлены в виде произведения условных потоковых/хроматических многочленов для каждой компоненты двусвязности. 2. Доказаны аналоги классических соотношений стягивания-удаления, получены различные модифицированные представления в виде знакопеременной суммы. Доказано знакочередование коэффициентов условного потокового и хроматического многочленов. Установлен комбинаторный смысл коэффициентов условного хроматического и потокового многочленов, впервые введено понятие нормального разреза, необходимое для формулировки последнего результата. Дан обзор результатов о связи матроидов и положительной математики со свойством Рэлея. 3. Представлен новый алгоритм для вычисления статистической суммы модели Поттса для параллельно-последовательных графов с произвольными весами. Описанный алгоритм использует преобразование графа «колье» в одно ребро, благодаря чему сложность алгоритма становится не более чем квадратичной по числу рёбер. Это выгодно отличает его от традиционных методов, основанных на формуле стягивания и удаления рёбер, для которых сложность растёт экспоненциально. 4. В 1977 Ю.В. Матиясевич получил формулу, выражающую хроматический полином произвольного графа как линейную комбинацию потоковых многочленов подграфов исходного графа. Показано, что это выражение является частным случаем просто доказываемой формулы, выражающей характеристический многочлен произвольного матроида через линейную комбинацию характеристических многочленов двойственных матроидов. В качестве приложений было получено явное выражение для потокового многочлена полного графа и формула для характеристического многочлена матроида, двойственного к матроиду проективной геометрии над конечным полем. Доказано, в частности, что их старшие коэффициенты задаются началом некоторой строки треугольника Паскаля. Первое выражение для графа K_n представляет собой сумму по всем разбиениям числа n, что (благодаря субэкспоненциальной асимптотики их количества, установленного Харди и Рамануджаном) позволило произвести полное явное вычисление коэффициентов потокового многочлена для n порядка 50. Подробно рассмотрена связь с формулами свертки и другими результатами для полиномов Татта, а также классическими формулами Рота для коэффициентов характеристического многочлена матроида. По результатам этого раздела имеется, в частности, публикация в журнале 2-го квартиля https://link.springer.com/article/10.1134/S1995080224604557 . 5. Пусть дан простой двусвязный плоский кубический граф G. Сопоставим каждой из 2n вершин этого графа переменную (спин), принимающую значения \pm 1. Хивуд доказал, что раскраска Тэйта, с точностью до выбора краски одного ребра, эквивалентна выбору значений спинов так, чтобы сумма этих значений в вершинах любой грани делилась на три. Эти условия задают систему линейных уравнений (СЛУ) с переменными, принимающими ненулевые значения в поле F_3. Множество вершин, значения спинов в которых однозначно определяют значения остальных спинов, назовем определяющим. Таковым, в частности, является множество вершин, соответствующих всем свободным переменным СЛУ. Из теоремы Хивуда следует, что количество раскрасок Тэйта не больше 3 2^{m(G)}, где m(G) - размер любого минимального определяющего множества. Мы обновили подход Хивуда, представив геометрическое доказательство того, что для недвудольного графа ранг СЛУ равен n+1, откуда m(G)<n в этом случае. Мы также доказали, что оценка 3 2^{m(G)} является точной: для каждого n>2 существует граф G с 2n вершинами с m(G)=n-2 и количеством раскрасок Тэйта 3 2^{n-2}. Важным результатом является альфа-представление для количества раскрасок Тэйта для рассматриваемого класса графов (их ненулевое число эквивалентно утверждению теоремы четырех красок). В рамках альфа-представления мы ввели новый объект - матрицу граней графа G и выразили количество раскрасок Тэйта через главные миноры этой матрицы. Результаты этого раздела представлены, в частности, в https://doi.org/10.48550/arXiv.2404.09347 . 6. Доказано, что для любого регулярного матроида значение его характеристического многочлена в точке q=p^d, где p – простое число может быть представлено в виде линейной комбинации символов Лежандра от значений производящей функции баз двойственного матроида над полем F_q. Это представление обобщает ранее полученное представление потокового многочлена в виде линейной комбинации символов Лежандра от производящей функции остовных деревьев графа (так называемое, альфа-представление), но имеет другое доказательство.

Аннотация результатов, полученных в 2025 году
В этом году нами получено несколько взаимосвязанных результатов исследований на стыке комбинаторики, математической физики и теории графов. 1. Алгебраическая двойственность для условных многочленов: За счет использование моделей Поттса, формализма потоков Биггса и методов конечных полей разработана общая алгебраическая двойственность для условных многочленов на языке преобразования Фурье. 2. Связь условных многочленов и V-полиномов Была доказана полная эквивалентность условных многочленов и V-полиномов, при определенном выборе параметров. Показано, что условные многочлены допускают представления, аналогичные статистическим суммам в моделях Поттса и потоковых моделях в формализме Биггса. Доказано, что полученные разложения совпадают с разложениями Фортейна–Кастелейна для соответствующих моделей. 3. Логарифмическая вогнутость коэффициентов условных хроматических и потоковых многочленов. • Доказана логарифмическая вогнутость для хордальных графов. • Доказана логарифмическая вогнутость для всех графов с двумя внешними вершинами. • Проведена полная компьютерная проверка для всех графов до 9 вершин включительно. Публикация: Статья с этими результатами, "Условные хроматические и потоковые многочлены: их комбинаторика и физические приложения", принята к печати в журнале "Теоретическая и математическая физика". 4. Связь с электрическими цепями и положительностью. Было установлена явная связь производящих функций рощ с минорами матриц отклика электрических сетей. Были найдены также специальные производящие функции рощ, которые специализируются на наиболее симметричных минорах матриц отклика. Эти миноры являются критерием циркулярной положительности для матриц отклика. Оказалось, что теже самые миноры и производящие функции рощ являются критерием положительности для точек положительного Грассманиана, связанных с электрическим сетями. Эти результаты описаны А.А. Казаковым в Разделе 4.6 статьи «Современная теория электрических сетей: от матричной теоремы о деревьях до теории кластерных многообразий», принятой к публикации в журнале "Успехи математических наук" Они пересекаются с докладом А.А. Казакова на конференции Eurocomb'25 (https://nextcloud.renyi.hu/index.php/s/TdjSmNjDjrQEH2X , pp. 456-460.) 5. В работе Мухамеджановой С.А. "A Mathematical-Model-Based algorithmic implementation for computing the Potts-Model partition function for series–parallel graphs" развита техника упрощения графов параллельно-последовательного типа, известная как necklace-reduction. Это позволило: построить эффективные алгоритмы вычисления статистических сумм модели Поттса на SP-графах; вывести новые явные формулы для этой модели; применить параллельно-последовательные преобразования в духе Сокала. 6. Получено альфа-представление для характеристических функций регулярных матроидов, представимых над конечным полем. Описана связь этого представления с альфа-представлением для количества векторов Хивуда (раскрасок Тэйта). Доказательства существенно упрощены по сравнению с первоначальной версией. Результаты представлены в статье "The α-representation for the Tait coloring and for the characteristic polynomial of matroid" в марте 25 года направлена в "The Electronic Journal of Combinatorics" (см. также https://arxiv.org/abs/2503.14285). 7. Обновлен подход Хивуда к перечислению раскрасок Тейта - представлено геометрическое доказательство того, что для недвудольного простой двусвязный плоский кубический графа ранг системы линейных уравнений Хивуда равен n+1, где n - количество вершин графа. Введено понятие определяющего множества вершин. Доазано, что количество раскрасок Тейта не больше 3 2^m, где m - размер любого минимального определяющего множества. Доказано также, что эта оценка является точной, она достижима на некотором классе графов. Эти результаты представлены в статье "Вектора Хивуда, определяющие множества вершин и матрица граней".