The minimum Manhattan distance and minimum jump of permutations

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