Заседание Московского математического общества 5 декабря 2017 г.

(начало в 18 час. 30 мин., ауд. 16-10 Главного здания МГУ)

Алгебраические методы в комбинаторике: многочлены и групповые кольца

Федор Петров

В игре "Сет" каждая из $3^n$ карт имеет $n$ признаков, принимающих по три различных значения. Тройка карт называется сетом, если по каждому признаку они либо все совпадают, либо все различны. Иными словами, сет - арифметическая прогрессия длины 3 в группе $G=Z_3^n$. Каков размер наибольшего возможного множества в этой группе, не содержащего сета?

Рот доказал оценку $o(3^n)$ с помощью гармонического анализа на указанной группе. Долгое время лучшими были оценки вроде $3^n/n$, пока в 2016 году не появилась работа Крута, Лива и Паха, в которой была доказана верхняя оценка $k^n$ при конкретном $k<4$ для группы $Z_4^n$. Вскоре замечательный метод этой работы, сочетающий полиномиальный метод в духе комбинаторной теоремы о нулях Алона, линейно-алгебраические соображения размерности и закон больших чисел, был приспособлен и к другим группам, в том числе и к $Z_3^n$ (Элленберг, Гийсвийт). Оказалось, что этот и другие комбинаторные результаты для группы $G$ тесно связаны со структурой делителей нуля в групповой алгебре группы $G$. Такой взгляд позволил докладчику включить в рассмотрение и некоммутативные группы.

Та же игра с многочленами, которая привела к этим результатам, чуть ранее применялась для таких задач перечислительной комбинаторики и анализа, как вычисление коэффициентов многочленов Лорана и интегралов типа Сельберга.

Категория: 
Наука