The Evolution of the Random Permutation

随机排列的演变

• 批准号: 2431519
• 金额: --
• 依托单位: University of Strathclyde
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2431519
• 关键词: Evolution; 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.

这个项目的目标是研究一个大型随机排列的结构是如何随着其倒置次数的增加而演变的。与鄂尔多斯-雷尼随机图的类似理论相比，这一理论受到的关注相对较少。一个跨数学和科学学科的共同观察是，满足给定约束集的大型随机对象往往看起来很相似。然后，共同的挑战是确定它们的结构，以便理解它们的行为。Erdos-Rényi随机图G(n，m)是随机对象中最有影响和最有成果的模型之一，它是从所有具有恰好m个边的n-顶点图中一致提取的。本文的目的是研究一种类似的随机排列模型：从所有恰好m个反转的n-置换中一致提取的[小写西格玛](n，m)。排列模型与随机图具有明显不同的性质，因为[小写西格玛](n，m)表现出在Erdos-Rényi图模型中没有遇到的显著的局部-全局二分法。随机排列也缺乏G(n，m)可用的自然概率和进化模型。一个特别的重点将是建立某些子结构(模式)几乎肯定地第一次出现的阈值。当求逆次数为次线性时，一个基本问题是确定任何给定子排列出现的门限，并确定它在出现窗口中的渐近分布。同样重要的还有更大的子结构何时出现的问题。进一步的重点将是构建适当的随机排列的概率和进化模型。另一个耐人寻味的问题涉及倒置次数和总位移之间的关系，这两者都是衡量排列与恒等式接近程度的自然指标。