на главную страницу ЛШСМ-2019 к списку курсов ЛШСМ-2019

Илья Жарков

Графы, критическая группа и многочлен Татта

И. Жарков планирует провести 4 занятия.

Мы начнем с классической банковской игры в рассыпание фишек (chip firing), также извесной как песочные модели; им два года назад был посвящён курс Никиты Калинина. В начальный момент на каждой вершине находится неотрицательное целое число фишек. На каждом ходу одна из вершин отдает по одной фишке каждому из своих соседей (а фишки, упавшие в некоторые выделенные вершины, пропадают насовсем), и этот процесс продолжается до тех пор, пока есть такие «богатые» вершины, которые можно рассыпать. Когда рассыпать уже нечего, получившееся состояние называется стабильным. Можно переходить от одного стабильного состояния к другому, сначала добавляя фишки, а потом рассыпая их. Но в некоторые состояния (например, в пустое) так вернуться нельзя. Те состояния, в которые можно вернуться откуда угодно, называются критическими. Оказывается, существуют другие объекты на графах, находящиеся во взаимно-однозначном соответствии с критическими конфигурациями. Эти объекты, а также всевозможные биекции между ними, и будут основной темой наших занятий.

Примерный план занятий:

  1. Банковские игры, критические конфигурации на графах, парковочные функции, остовные деревья, теорема Кэли для полных графов.
  2. Многочлен Татта, различные его определения и свойства, а также смысл его некоторых специализаций и значений.
  3. Алгоритм Дара и его обобщения, различные известные (и неизвестные) биекции между парковочными функции, деревьями и мономами в многочлене Татта.
  4. Графы как тропические кривые, теоремы Абеля–Якоби и Римана–Роха, замощения зонотопа (Якобиана) и биекции клеток с элементами критической группы.

Весь материал несложный, глубоких предварительных знаний не требует, в основном, рассчитан на учащихся старших классов. Некоторое знакомство с линейной алгеброй и абелевыми группами может быть полезным.

Литература: