论文标题
可重复的模式和发电机的最大多样性在简化的单词中
Repeatable patterns and the maximum multiplicity of a generator in a reduced word
论文作者
论文摘要
我们研究简单换位$ s_k =（k \：k+1）$的最大乘数$ \ nathcal {m}（k，n）$在简化的单词中，最长的置换$ w_0 = n \：n-1 \：n-1 \：n-1 \：\ cdots \：\ cdots \：2 \：2 \：2 \：1 $，与以前的问题相关，与网络相关的问题，以及k $ k $ k $ k $ k $ k $ - 在根据单调弱分离的路径重新解释问题后，我们表明，对于固定的$ k $和足够大的$ n $，最佳密度是通过精确含义的周期性的路径实现的，因此\ [\ nathcal {m}（m}（k，k，k，k，k，k，n）= c_k n + p_k（n + p_k（n + p_k（n）$ p_ $ p_k $ p_k $ p_k $ c_k $ p_k $和co $ p_k $ p p y＆c。实际上，我们表明$ c_k $始终是合理的，并使用“可重复的模式”计算此数量的几个界限和精确值，我们将介绍。
We study the maximum multiplicity $\mathcal{M}(k,n)$ of a simple transposition $s_k=(k \: k+1)$ in a reduced word for the longest permutation $w_0=n \: n-1 \: \cdots \: 2 \: 1$, a problem closely related to much previous work on sorting networks and on the "$k$-set" problem. After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed $k$ and sufficiently large $n$, the optimal density is realized by paths which are periodic in a precise sense, so that \[ \mathcal{M}(k,n)=c_k n + p_k(n) \] for a periodic function $p_k$ and constant $c_k$. In fact we show that $c_k$ is always rational, and compute several bounds and exact values for this quantity with "repeatable patterns", which we introduce.
