论文标题
双宽度VII：组
Twin-width VII: groups
论文作者
论文摘要
Twin Width是最近引入的图形参数，其中具有算法，组合和有限模型理论的应用。对于有界程度的图，通过准静电法保留了双宽度的有限性。因此，通过Cayley图，它定义了一个组不变。我们证明，Abelian，双曲线，有序，可解决或多项式生长的组具有有限的双宽度。可以通过排除组元素的产物自我行动中的模式来表征双宽度。基于这种特征，我们提出了一种称为统一双宽度的加强，该加强在诸如组扩展，直接产物和直接限制之类的结构下是稳定的。 有限生成的具有无限双宽度的群体的存在不是立即的。我们使用osajda的结果构建一个，将图形嵌入组成组。这意味着存在一类有限图的有限图，但包含$ 2^{o（n）} \ cdot n！$ graphs in vertex set $ \ {1，\ dots，n \} $上的$ 2^{o（n）} \ cdot n！$ graphs，在先前工作中解决了一个问题。
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasi-isometry. Thus, through Cayley graphs, it defines a group invariant. We prove that groups which are abelian, hyperbolic, ordered, solvable, or with polynomial growth, have finite twin-width. Twin-width can be characterised by excluding patterns in the self-action by product of the group elements. Based on this characterisation, we propose a strengthening called uniform twin-width, which is stable under constructions such as group extensions, direct products, and direct limits. The existence of finitely generated groups with infinite twin-width is not immediate. We construct one using a result of Osajda on embeddings of graphs into groups. This implies the existence of a class of finite graphs with unbounded twin-width but containing $2^{O(n)} \cdot n!$ graphs on vertex set $\{1,\dots,n\}$, settling a question asked in a previous work.
