Abstract
The structure of all the permutations of a sequence can be represented as a permutohedron, a graph where vertices are permutations and two vertices are linked if a swap of adjacent elements in the permutation of one of the vertices produces the permutation of the other vertex. It has been hypothesized that word orders in languages minimize the swap distance in the permutohedron: given a source order, word orders that are closer in the permutohedron should be less costly and thus more likely. Here we explain how to measure the degree of optimality of word order variation with respect to swap distance minimization. We illustrate the power of our novel mathematical framework by showing that crosslinguistic gestures are at least $77\%$ optimal. It is unlikely that the multiple times where crosslinguistic gestures hit optimality are due to chance. We establish the theoretical foundations for research on the optimality of word or gesture order with respect to swap distance minimization in communication systems. Finally, we introduce the quadratic assignment problem (QAP) into language research as an umbrella for multiple optimization problems and, accordingly, postulate a general principle of optimal assignment that unifies various linguistic principles including swap distance minimization.
Abstract (translated)
一个序列的所有排列结构可表示为排列多面体（permutohedron），这是一种图结构：顶点代表排列，若一个顶点的排列中相邻元素交换后得到另一顶点的排列，则两顶点相连。有假说认为，语言中的词序会最小化排列多面体中的交换距离：给定一个源词序，在排列多面体中交换距离更近的词序成本更低，因而更可能出现。本文阐释了如何衡量词序变异在交换距离最小化方面的最优程度。通过证明跨语言手势至少达到77%的最优性，我们展示了这一新数学框架的效力。跨语言手势多次达到最优性不太可能出于偶然。我们为研究通信系统中词序或手势序在交换距离最小化方面的最优性奠定了理论基础。最后，我们将二次分配问题（QAP）引入语言研究，作为统摄多种优化问题的框架，并据此提出一个统一多种语言学原则（包括交换距离最小化）的一般最优分配原则。
URL
https://arxiv.org/abs/2604.01938
