Context-free graphs and their transition groups

2024/08/23 by D'Angeli, Daniele, Matucci, Francesco, Perego, Davide +1 · 2 citations
#05C75 #20F10 #20F65 #68Q70 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2408.13070

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 co-word 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 poly-context-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.

Cited by

• A graph-theoretical characterisation of subgroups of Thompson's group V
• On context-free subgroups and R. Thompson's group V

Related

• Closure Properties in the Class of Multiple Context Free Groups
• Context-Free Groups and Bass-Serre Theory
• The topology and geometry of automorphism groups of free groups
• Virtual retractions in free constructions
• The generalised word problem for subgroups of hyperbolic groups