Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary

It can be shown that each permutation group $G⊑S_n$ can be embedded, in a well defined sense, in a connected graph with $O(n+|G|)$ vertices. Some groups, however, requi…