Cayley graphs are a type of combinatorial encoding of a group, where the elements of the group become vertices, and the edges connect those elements that are obtained from each other by multiplying by one of the generators of the group. This allows us to study the structure of groups using graph theory methods; in particular, to search for approaches to solving word problems for different groups (i.e., comparing structures modulo rewriting rules). Variations of this class of problems are normalization and unification in programming language theory (PLT). It is also interesting that Cayley graphs are an example of the Para-construction from applied category theory.
Some introductory material:
- Konstantinova, “Lecture notes on Algebraic Graph Theory”
- Konstantinova, “Three problems on Cayley graphs”
Recently, a number of works have appeared on the application of machine learning to finding the shortest paths on such graphs (some of them in Russian):
- Хоружий, “Введение в методы поиска короткого пути на больших графах”
- Дурыманов, “Cayley2vec - эмбединги для бесконечных графов”
- Obozov, “PPO и не только в приложении к графам”
- Chervov et al, [2025] “A Machine Learning Approach That Beats Large Rubik’s Cubes”
- Chervov et al, [2025] “CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs”
- Лыткин, “Применение методов машинного обучения для поиска путей в графах Кэли”