The minimum Manhattan distance and minimum jump of permutations

Abstract

Let $\pi$ be a permutation of $\{1,2,\dots ,n\}$. If we identify a permutation with its graph, namely the set of $n$ dots at positions $(i,\pi (i))$, it is natural to consider the minimum $L^1$ (Manhattan) distance, $d(\pi )$, between any pair of dots. The paper computes the expected value (and higher moments) of $d(\pi )$ when $n\to \infty$ and $\pi$ is chosen uniformly, and settles a conjecture of Bevan, Homberger and Tenner (motivated by permutation patterns), showing that when $d$ is fixed and $n\to \infty$, the probability that $d(\pi )\ge d+2$ tends to $e^{-d^2-d}$. The minimum jump $mj(\pi )$ of $\pi$, defined by $mj(\pi )={\min }_{1\le i\le n-1}|\pi (i+1)-\pi (i)|$, is another natural measure in this context. The paper computes the asymptotic moments of $mj(\pi )$, and the asymptotic probability that $mj(\pi )\ge d+1$ for any constant $d$.

20 pages, 3 figures. Minor changes throughout