论文标题
翻转图
Flip Graphs
论文作者
论文摘要
翻转图是组合对象上的图形，其中邻接关系反映了基础对象的局部变化。在本论文中，我们介绍了轭图，这是一个翻转图的家族，该家族在无色三角形的三角形，弧排列和几何毛毛虫上概括了先前研究的翻转图家族。我们的主要结果是计算任意轭图的直径以及该图家族的自动形态组的完整表征。我们还表明，oke图是$ \ tilde {c} _m $ offine weyl offine weyl组的Schreier图。 我们在直径计算中采用的方法不同于用于无色三角形三角形和弧排列的方法。我们表明，用于ARC置换图的方法不会扩展到轭图。我们证明的核心是将直径评估转变为偏心率问题的想法。自动形态群的表征是上述三个特殊轭图系列的新结果。
Flip graphs are graphs on combinatorial objects in which the adjacency relation reflects a local change in the underlying objects. In this thesis we introduce Yoke graphs, a family of flip graphs that generalizes previously studied families of flip graphs on colored triangle-free triangulations, arc permutations and geometric caterpillars. Our main results are the computation of the diameter of an arbitrary Yoke graph and a full characterization of the automorphism group of this family of graphs. We also show that Yoke graphs are Schreier graphs of the affine Weyl group of type $\tilde{C}_m$. The approach we take in the computation of the diameter is different from the ones used for colored triangle-free triangulations and arc permutations. We show that the approach used for arc permutation graphs does not extend to Yoke graphs. At the heart of our proof lies the idea of transforming a diameter evaluation into an eccentricity problem. The characterization of the automorphism group is a new result for the above mentioned three special families of Yoke graphs.
