# How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization

arXiv: https://arxiv.org/abs/2604.01938 · HTML: https://mlsanity.com/paper/2604.01938/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 86 references that are in the map.
- First posted on arXiv 2 Apr 2026.

## Builds on (most cited first, 20 of 20)

- [Contrasting Linguistic Patterns in Human and LLM-Generated News Text](https://mlsanity.com/paper/2308.09067/) (2023)
- [The optimality of syntactic dependency distances](https://mlsanity.com/paper/2007.15342/) (2020)
- [Optimal coding and the origins of Zipfian laws](https://mlsanity.com/paper/1906.01545/) (2019)
- [Minimum projective linearizations of trees in linear time](https://mlsanity.com/paper/2102.03277/) (2021)
- [The placement of the head that minimizes online memory: a complex systems approach](https://mlsanity.com/paper/1309.1939/) (2013)
- [The scarcity of crossing dependencies: a direct outcome of a specific constraint?](https://mlsanity.com/paper/1601.03210/) (2016)
- [Kauffman's adjacent possible in word order evolution](https://mlsanity.com/paper/1512.05582/) (2015)
- [Memory limitations are hidden in grammar](https://mlsanity.com/paper/1908.06629/) (2019)
- [Compression as a universal principle of animal behavior](https://mlsanity.com/paper/1303.6175/) (2013)
- [Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees](https://mlsanity.com/paper/2107.03277/) (2021)
- [Linguistic laws in biology](https://mlsanity.com/paper/2310.07387/) (2023)
- [Swap distance minimization in SOV languages. Cognitive and mathematical foundations](https://mlsanity.com/paper/2312.04219/) (2023)
- [Transitive Reduction of Citation Networks](https://mlsanity.com/paper/1310.8224/) (2013)
- [Direct and indirect evidence of compression of word lengths. Zipf's law of abbreviation revisited](https://mlsanity.com/paper/2303.10128/) (2023)
- [Swap distance minimization beyond entropy minimization in word order variation](https://mlsanity.com/paper/2404.14192/) (2024)
- [A stronger null hypothesis for crossing dependencies](https://mlsanity.com/paper/1410.5485/) (2014)
- [Corrections of Zipf's and Heaps' Laws Derived from Hapax Rate Models](https://mlsanity.com/paper/2307.12896/) (2023)
- [The expected sum of edge lengths in planar linearizations of trees. Theory and applications](https://mlsanity.com/paper/2207.05564/) (2022)
- [The optimality of word lengths. Theoretical foundations and an empirical study](https://mlsanity.com/paper/2208.10384/) (2022)
- [The exponential distribution of the order of demonstrative, numeral, adjective and noun](https://mlsanity.com/paper/2502.06342/) (2025)

## Built on by (most cited first, 1 of 1)

- [Swap distance minimization shapes the order of subject, object and verb in languages of the world](https://mlsanity.com/paper/2604.26726/) (2026)

## Abstract (arXiv)

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 examining spontaneous gestures produced by speakers from four languages (two SVO languages and two VSO languages, which represent two linguistic families). We show 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.