Рост графов и групп

Понятие роста является одним из центральных в математике и используется в различных вариациях практически во всех ее разделах. Что такое рост функции понятно любому грамотному старшекласнику. Также ясно, что его использование актуально во многих перечислительных (и не только) задачах комбинаторики. Менее очевидно как его применять в алгебре, в частности, в теории групп.
Я попытаюсь объяснить это начав с теории графов — где определение роста графа наглядно. Но вначале мы немного задержимся на понятии дилатационного сравнения функций. В качестве интересного примера графов, ведущего также к замечательным пример групп, я рассмотрю семейство графов, которое возникает при изучении математической модели детской (и не только) игры «Ханойские башни». Затем я переду к группам, где, после краткого напоминания что это такое и простых примеров, объясню как с группой заданной системой образующих можно ассоциировать граф, называющийся графом Кэли. Рост группы можно определить как рост ее графа Кэли.
Теория роста групп берет начало с работ А.С.Шварца и Дж. Милнора и изобилует красивыми и глубокими результатами, а также трудными нерешенными проблемами. После перечисления некоторых из основных результатов в этой области, в частности теоремы М.Громова, характеризующей группы со степенным ростом, я перейду к проблеме Милнора о существовании групп промежуточного роста между экспоненциальным и степенным. Будет рассказано как эта проблема была решена докладчиком, а также какие основные факты о группах промежуточного роста известны. Закончу я лекцию формулировкой нескольких нерешенных проблем.