论文标题
可拆卸的排列，脱卸额和无环方向
Toppleable Permutations, Excedances and Acyclic Orientations
论文作者
论文摘要
回想一下，排列$π$的发出是任何位置$ i $，以便$π_i> i $。受霍普金斯（Hopkins），麦康维尔（McConville）和PROPP（Elec。J.Comb。，2017）的作品的启发，我们说，如果通过一系列倒数动作进行排序，则置换量是可以推翻的。我们的主要结果之一是，$ n $字母上的可拆下排列数与exceDances完全在$ \ {1，\ dots，\ lfloor（n-1）/2 \ rfloor \} $相同。此外，我们表明以上也是具有独特的汇（Ausos）的无环方向的数量，完整的两部分图$ k _ {\ lceil n/2 \ rceil，\ lfloor n/2 \ rfloor + 1} $。我们还为完整的多部分图的澳大利亚人数提供了一个公式。最后，我们对Cameron等人的极端问题进行了观察。关于（给定）循环的最大化器（数量）的最大值，给定图形的规定数量的顶点和边缘。
Recall that an excedance of a permutation $π$ is any position $i$ such that $π_i > i$. Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. One of our main results is that the number of toppleable permutations on $n$ letters is the same as those for which excedances happen exactly at $\{1,\dots, \lfloor (n-1)/2 \rfloor\}$. Additionally, we show that the above is also the number of acyclic orientations with unique sink (AUSOs) of the complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}$. We also give a formula for the number of AUSOs of complete multipartite graphs. We conclude with observations on an extremal question of Cameron et al. concerning maximizers of (the number of) acyclic orientations, given a prescribed number of vertices and edges for the graph.
