Аннотация:
В математике автомат — это не оружие и не устройство. Это — направленный граф с $n$ вершинами, ребра которого раскрашены в $k$ цветов. Из каждой вершины выходят ровно $k$ ребер, по одному каждого цвета. Конечная последовательность цветов называется «словом перезагрузки», если, выходя из произвольной вершины и проходя по ребрам соответствующих цветов, мы оказываемся в одном и том же месте. Таким образом, последовательность команд (цветов) задает перезагрузку системы: она приходит в одно и то же состояние (вершину), не зависимо от того, в каком состоянии находилась.
Как понять, есть ли у графа слово перезагрузки, и если да — то какой длины? Гипотеза, выдвинутая в 1964 Яном Черны утверждает, что если перезагрузка существует, то её всегда можно выполнить словом длины не более $(n-1)^2$. Эту оценку нельзя улучшить! Гипотеза остается открытой, однако кое-что удается выяснить. Мы покажем аналитический подход к данной проблеме, в котором теория графов причудливым образом сойдется с выпуклой геометрией, функциональными уравнениями, и даже с фракталами. В результате будет найдены достаточные условия для существования слова перезагрузки.
Они, в частности, объяснят, почему для большинства графов такое слово существует.
Слушателям желательно знать что такое матрица и линейное преобразование. Остальное объясним.
