The Evolution of the Random Permutation

该项目的目标是研究大型随机排列的结构如何随着其反转数量的增加而演变。与erdos - rsamnyi随机图的类似理论相比，这一理论受到的关注相对较少。一个在数学和科学学科中共享的观察结果是，满足给定约束集的大型随机对象往往看起来很相似。共同的挑战是确定它们的结构，以便了解它们的行为。erdos - rsamnyi随机图G（n,m）是最有影响力和最有成果的随机对象模型之一，它从所有恰好有m条边的n顶点图中均匀绘制而成。本博士的目的是研究随机排列的类似模型：[小写sigma]（n,m）从所有n个排列中均匀抽取，具有m个反转。排列模型与随机图具有明显不同的性质，因为[小写sigma]（n,m）表现出erdos - rsamnyi图模型中没有遇到的显著的局部-全局二分法。随机排列也缺乏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.