84 подписчика
Любая группа реализуется как группа автоморфизмов какого-то графа (для конечных груп это довольно просто)
Если выбрать в группе G систему порождающих S, то группа автомофорфизов раскрашенного графа Кэли
[рассматриваемого как ориентированный граф с ребрами раскрашенными в S цветов] совпадает с G
Это верно для любой группы
Теперь надо заменить каждое ориентированное ребро цвета C на подграф [неориентируемый нераскрашенный] с двумя выходами который не имеет автоморфизмов и который достаточно связный чтобы его нельзя было разрезать на две части перерезав одно ребро [кажется все]. такой может отображаться только в свою копию которая стоит на месте ребра с нужной ориентацией и цветом
Это теорема Фрухта
Есть целая индустрия по трансферу симметрий из одной категории [чаще всего графов] в другую
для модулей [Gobel], полей [Fried-Kollar], алгебр эндоморфизмов [Trlifaj]
---
Вот еще по теме
A Computable Functor From Graphs to Fields
Russell Miller, Bjorn Poonen, Hans Schoutens, Alexandra Shlapentokh
We construct a fully faithful functor from the category of graphs to the category of fields. Using this functor, we resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure S, there exists a countable field F with the same essential computable-model-theoretic properties as S
Along the way, we develop a new "computable category theory," and prove that our functor and its partially-defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors
1 минута
21 мая