Sorting via Chip-Firing
Sorting via Chip-Firing
复制标题
通过芯片烧制进行分类
DOI：
--
复制
发表时间：
2016
影响因子：
0.7
通讯作者：
J. Propp
中科院分区：
文献类型：
--
作者：
S. Hopkins;T. McConville;J. Propp
我们研究了无限路径图$mathbb{Z}$上的芯片点火过程的一个变体：我们不是将芯片视为不可区分的，而是用正整数来标记它们。要激发不稳定的顶点，即具有多个芯片的顶点，我们在该顶点选择任意两个芯片，并将标记较少的芯片移动到左侧，将标记较大的芯片移动到右侧。这种标记版本的芯片烧制过程显示出显著的汇流特性，类似于但比未标记芯片烧制普遍存在的汇流特性更微妙：当所有芯片从原点开始且芯片数量为偶数时，芯片总是以有序的顺序结束。我们的排序证明依赖于一个关于未标记芯片发射的独立有趣的引理，该引理认为稳定化保持了配置上的自然偏序。我们还讨论了这种排序现象对其他图(无限路径的变体)、其他初始构型和其他Cartan-Killing型的一些扩展。
We investigate a variant of the chip-firing process on the infinite path graph $mathbb{Z}$: rather than treating the chips as indistinguishable, we label them with positive integers. To fire an unstable vertex, i.e. a vertex with more than one chip, we choose any two chips at that vertex and move the lesser-labeled chip to the left and the greater-labeled chip to the right. This labeled version of the chip-firing process exhibits a remarkable confluence property, similar to but subtler than the confluence that prevails for unlabeled chip-firing: when all chips start at the origin and the number of chips is even, the chips always end up in sorted order. Our proof of sorting relies upon an independently interesting lemma concerning unlabeled chip-firing which says that stabilization preserves a natural partial order on configurations. We also discuss some extensions of this sorting phenomenon to other graphs (variants of the infinite path), to other initial configurations, and to other Cartan-Killing types.