Context‐free graphs and their transition groups
Daniele D’Angeli, Francesco Matucci, Davide Perego, Emanuele Rodaro · Transactions of the London Mathematical Society · 2026
Abstract Starting from context‐free inverse graphs, we introduce a new class of groups and study their structural properties. We establish closure properties, show that their coword problems are context‐free, analyze torsion elements, and realize them as subgroups of the asynchronous rational group. Context‐freeness is preserved under a generalized free product of graphs, and using this construction, we provide examples of groups that are not residually finite or not polycontext‐free, making them relevant for testing the Lehnert and Brough conjectures. Moreover, we investigate how small local modifications of a graph affect the global structure of the transition group, showing that for locally quasi‐transitive graphs with infinite orbits, the transition group decomposes into a highly structured quotient by a bounded torsion subgroup, showing strong global constraints induced by local graph properties.