Permutations with few inversions are locally uniform
Bevan, David (2019) Permutations with few inversions are locally uniform. Discrete Analysis. ISSN 23973129

Text (BevanArXiv2019Permutationswithfewinversionsarelocally)
Bevan_ArXiv_2019_Permutations_with_few_inversions_are_locally.pdf Preprint Download (328kB) Preview 
Abstract
We prove that permutations with few inversions exhibit a localglobal dichotomy in the following sense. Suppose σ is a permutation chosen uniformly at random from the set of all permutations of [n] with exactly m = m(n) ≪ n2 inversions. If i < j are chosen uniformly at random from [n], then σ (i) < σ (j) asymptotically almost surely. However, if i and j are chosen so that j  i ≪ m/n, and m ≪ n2/log2n, then limn→∞ P [ σ (i) < σ (j)] = ½. Moreover, if k = k(n) ≪ √(m/n), then the restriction of σ to a random kpoint interval is asymptotically uniformly distributed over Sk. Thus, knowledge of the local structure of σ reveals nothing about its global form. We establish that √(m/n) is the threshold for local uniformity and m/n the threshold for inversions, and determine the behaviour in the critical windows.
Creators(s):  Bevan, David ORCID: https://orcid.org/0000000171792285; 

Item type:  Article 
ID code:  72724 
Keywords:  permutations, inversions, Mathematics, Discrete Mathematics and Combinatorics 
Subjects:  Science > Mathematics 
Department:  Faculty of Science > Mathematics and Statistics 
Depositing user:  Pure Administrator 
Date deposited:  11 Jun 2020 13:41 
Last modified:  12 Jul 2020 02:32 
Related URLs:  
URI:  https://strathprints.strath.ac.uk/id/eprint/72724 
Export data: 