The Evolution of the Random Permutation

点击翻译按钮获取中文摘要

The goal of this project is to investigate how the structure of a large random permutation evolves as the number of its inversions increases. This has received comparatively little attention in comparison to the analogous theory of the Erdos-Rényi random graph.An observation shared across mathematical and scientific disciplines is that large random objects satisfying a given set of constraints tend to look alike. The common challenge is then to determine their structure so as to understand their behaviour. One of the most influential and fruitful models of random objects has been the Erdos-Rényi random graph G(n,m), drawn uniformly from all n-vertex graphs with exactly m edges.The aim of this PhD is to study an analogous model of the random permutation: [lowercase sigma](n,m) drawn uniformly from all n-permutations with exactly m inversions. The permutation model is of a manifestly different nature from the random graph, because [lowercase sigma](n,m) exhibits a striking local-global dichotomy not encountered in the Erdos-Rényi graph model. The random permutation also lacks the natural probabilistic and evolutionary models available for G(n,m).A particular focus will be on establishing the thresholds at which certain substructures ("patterns") first appear asymptotically almost surely. A fundamental question when the number of inversions is sublinear is to establish the threshold for the appearance of any given subpermutation, and determine its asymptotic distribution in the window of its emergence. Also of importance are questions about when larger substructures first appear.A further emphasis will be on constructing suitable probabilistic and evolutionary models of the random permutation. Another intriguing question concerns the relationship between the number of inversions and the total displacement, both of which are natural measures of how close a permutation is to the identity.