Илья Жарков

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

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

Мы начнем с классической банковской игры в рассыпание фишек (chip firing), также известной как песочные модели; им два года назад был посвящён курс Никиты Калинина.

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

 

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

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

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

Литература:

  • N. L. Biggs, Chip-Firing and the Critical Group of a Graph, Journal of Algebraic Combinatorics, Volume 9 Issue 1, 1999, 25-45.
  • A. Goodall and J. Nešetřil, Graph invariants homomorphisms and the Tutte polynomials, https://iuuk.mff.cuni.cz/~andrew/HomProfiles.pdf
  • G. Mikhalkin and I. Zharkov, Tropical curves, their Jacobians and Theta functions, in Curves and Abelian Varieties, Contemporary Mathematics, Vol. 465, AMS 2008, 203-230.
  • Н.Калинин, записки курса 2017 года

Organization Committee e-mail:
dubna@mccme.ru