Postgraduate research opportunities

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 Erdős–Rényi random graph.

Number of places

1

Opens

27 February 2020

Duration

3 years

Eligibility

You should have (or expect to have) a UK Honours Degree (or equivalent) at 2.1 or above in Mathematics or a closely related subject with a high mathematical content.

Project Details

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 Erdős–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: sigma(n, m) drawn uniformly from all n-permutations with exactly m inversions [1]. The random permutation behaves rather differently from the random graph, exhibiting a local–global dichotomy not present with graphs [2]. It also lacks the natural probabilistic and evolutionary models available for the random graph.

A particular focus will be on establishing the thresholds at which certain substructures 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 [3].

[1] H. Acan and B. Pittel. On the connected components of a random permutation graph with a given number of edges. J. Combin. Theory Ser. A, 120(8), 2013.

[2] D. Bevan. Permutations with few inversions are locally uniform. https://arxiv.org/pdf/1908.07277

[3] D. Bevan. The curious behaviour of the total displacement. https://tinyurl.com/tdrTalk