论文标题
将置换组压缩到语法和多面体中。图形嵌入方法
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
论文作者
论文摘要
可以证明，每个排列组$ g \ sqsubseteq s_n $可以从定义明确的意义上嵌入，并在带有$ o（n+| g |）$ vertices的连接图中嵌入。但是，一些小组需要更少的顶点。例如，$ s_n $本身可以嵌入到$ n $ clique $ k_n $中，这是带有n个顶点的连接图。在这项工作中，我们表明，无上下文的语法生成有限置换组$ g \ sqsubseteq s_n $的最小尺寸可以由嵌入$ g $的三个结构性参数上限为上限：嵌入$ g $的三个结构性参数：顶点的数量，顶点，树宽和最大程度。更准确地说，我们表明，任何置换组$ g \ sqsubseteq s_n $都可以嵌入具有$ m $ $ pertices，treewidth k和最高度$δ$的连接图中，也可以由上下文的无上下文的语法生成，该语法$ 2^{o（kΔ\logΔ）通过将我们的上限与置换组的扩展复杂性与形式语言的语法复杂性之间的联系结合在一起，我们还可以获得这些排列组可以通过扩展复杂性的多型$ 2^{o（kδ\logΔ）} \ cdot m^{o（k）} $表示。上面的上限可用于在排列组的索引之间以及嵌入这些组的连接图的顶点，树宽和最大程度的连接图之间提供权衡。特别是，通过将我们的主要结果与著名的$ 2^{ω（n）} $结合在对称群体的语法复杂性上，我们拥有的对称群体的语法复杂性，我们拥有的treewidth $ o（n/\ log n）$的连接图（n/\ log log n）$和最大程度$ o（n/\ n/\ log n/\ log n/\ log n log n log nog nog nog nog sy $ s_n $ s_ $ s_ $ s_ $ s_n $ 2^$ s_n $ 2^$ 2^$ 2^$ 2^^$ 2^^$ c. $ n^{ω（1）} $ VERTICES。对于$ \ varepsilon <1 $和最大程度$ o（n/\ log n）$，可以将此较低的限制改进到TreeWidth $ n^{\ varepsilon} $上的指数上。
It can be shown that each permutation group $G \sqsubseteq S_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, $S_n$ itself can be embedded in the $n$-clique $K_n$, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group $G \sqsubseteq S_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 \sqsubseteq S_n$ that can be embedded into a connected graph with $m$ vertices, treewidth k, and maximum degree $Δ$, can also be generated by a context-free grammar of size $2^{O(kΔ\logΔ)}\cdot m^{O(k)}$. By combining our upper bound with a connection 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 Δ)}\cdot m^{O(k)}$. The above upper bounds can be used to provide trade-offs 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 $S_n$ we have that connected graphs of treewidth $o(n/\log n)$ and maximum degree $o(n/\log n)$ embedding subgroups of $S_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^{\varepsilon}$ for $\varepsilon<1$ and maximum degree $o(n/\log n)$.
