|
|
Заседания Московского математического общества
5 декабря 2017 г., г. Москва, ГЗ МГУ, аудитория 16-10
|
|
|
|
|
|
Алгебраические методы в комбинаторике: многочлены и групповые кольца
Ф. В. Петров |
Количество просмотров: |
Эта страница: | 408 |
Фотогалерея
|
Аннотация:
В игре «Сет» каждая из $3^n$ карт имеет $n$ признаков, принимающих по три различных значения. Тройка карт называется сетом, если по каждому признаку они либо все совпадают, либо все различны. Иными словами, сет — арифметическая прогрессия длины 3 в группе $G=\mathbb Z_3^n$. Каков размер наибольшего возможного множества в этой группе, не содержащего сета?
Рот доказал оценку $o(3^n)$ с помощью гармонического анализа на указанной группе. Долгое время лучшими были оценки вроде $3^n/n$, пока в 2016 году не появилась работа Крута, Лива и Паха, в которой была доказана верхняя оценка $k^n$ при конкретном $k<4$ для группы $\mathbb Z_4^n$. Вскоре замечательный метод этой работы, сочетающий полиномиальный метод в духе комбинаторной теоремы о нулях Алона, линейно-алгебраические соображения размерности и закон больших чисел, был приспособлен и к другим группам, в том числе и к $\mathbb Z_3^n$ (Элленберг, Гийсвийт). Оказалось, что этот и другие комбинаторные результаты для группы $G$ тесно связаны со структурой делителей нуля в групповой алгебре группы $G$. Такой взгляд позволил докладчику включить в рассмотрение и некоммутативные группы.
Та же игра с многочленами, которая привела к этим результатам, чуть ранее применялась для таких задач перечислительной комбинаторики и анализа, как вычисление коэффициентов многочленов Лорана и интегралов типа Сельберга.
|
|