Jaffke, Lars ;
de Oliveira Oliveira, Mateus ;
Tiwary, Hans Raj
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
Abstract
It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+G) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can be embedded in the nclique K_n, a connected graph with n vertices.
In this work, we show that the minimum size of a contextfree grammar generating a finite permutation group G⊑ 𝕊_n can be upper bounded by three structural parameters of connected graphs embedding G: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group G ⊑ 𝕊_n that can be embedded into a connected graph with m vertices, treewidth k, and maximum degree Δ, can also be generated by a contextfree grammar of size 2^{O(kΔlogΔ)}⋅ m^{O(k)}. By combining our upper bound with a connection established by Pesant, Quimper, Rousseau and Sellmann [Gilles Pesant et al., 2009] between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity 2^{O(kΔlogΔ)}⋅ m^{O(k)}.
The above upper bounds can be used to provide tradeoffs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated 2^{Ω(n)} lower bound on the grammar complexity of the symmetric group 𝕊_n due to Glaister and Shallit [Glaister and Shallit, 1996] we have that connected graphs of treewidth o(n/log n) and maximum degree o(n/log n) embedding subgroups of 𝕊_n of index 2^{cn} for some small constant c must have n^{ω(1)} vertices. This lower bound can be improved to exponential on graphs of treewidth n^{ε} for ε < 1 and maximum degree o(n/log n).
BibTeX  Entry
@InProceedings{jaffke_et_al:LIPIcs:2020:12716,
author = {Lars Jaffke and Mateus de Oliveira Oliveira and Hans Raj Tiwary},
title = {{Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {50:150:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12716},
URN = {urn:nbn:de:0030drops127161},
doi = {10.4230/LIPIcs.MFCS.2020.50},
annote = {Keywords: Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity}
}
18.08.2020
Keywords: 

Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 