The Evolution of the Random Permutation
Lead Research Organisation:
University of Strathclyde
Department Name: Mathematics and Statistics
Abstract
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.
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.
Organisations
People |
ORCID iD |
David Bevan (Primary Supervisor) | |
Daniel Threlfall (Student) |
Studentship Projects
Project Reference | Relationship | Related To | Start | End | Student Name |
---|---|---|---|---|---|
EP/V520032/1 | 01/10/2020 | 31/10/2025 | |||
2431519 | Studentship | EP/V520032/1 | 01/10/2020 | 30/09/2024 | Daniel Threlfall |