The Evolution of the Random Permutation

这个项目的目标是研究一个大的随机排列的结构如何随着其反转数的增加而演变。与类似的Erdos-Rényi随机图理论相比，这一点很少受到关注。数学和科学学科都有一个共同的观察结果，即满足给定约束条件的大型随机对象往往看起来很相似。因此，共同的挑战是确定它们的结构，以便了解它们的行为。Erdos-Rényi随机图G（n，m）是随机对象的最有影响力和最有成果的模型之一，它是从所有具有恰好m条边的n-顶点图中均匀抽取的。本博士论文的目的是研究随机置换的类似模型：[Σ sigma]（n，m）是从所有具有恰好m个反转的n-置换中均匀抽取的。置换模型与随机图有着明显不同的性质，因为[Σ Σ]（n，m）表现出一个在Erdos-Rényi图模型中没有遇到的显著的局部-全局二分法。随机置换也缺乏G（n，m）可用的自然概率和进化模型。一个特别的重点将是建立阈值，在该阈值处，某些子结构（“模式”）几乎肯定地第一次渐近出现。一个基本的问题时，反转的数量是次线性的是建立阈值的出现任何给定的子置换，并确定其渐近分布在其出现的窗口。更重要的是，当较大的子结构首次出现的问题。进一步的重点将是建立合适的随机排列的概率和进化模型。另一个有趣的问题涉及反转的数量和总位移之间的关系，这两者都是排列与恒等式接近程度的自然度量。

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.