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

Funding

Home fee, Stipend

Opens

27 February 2020

Deadline

12 June 2020

Duration

4 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.

Eligibility for RCUK studentships

  • Research Council (RC) fees and stipend can only be awarded to UK and EU students and not to EEA or International students.
  • EU students are only eligible for RC stipend if they have been resident in the UK for 3 years, including for study purposes, immediately prior to starting their PhD.
  • If an EU student cannot fulfil this condition then they are eligible for a fees only studentship.
  • International students cannot be funded from RC funds unless they are ‘settled’ in the UK. ‘Settled’ means being ordinarily resident in the UK without any immigration restrictions on the length of stay in the UK. To be ‘settled’ a student must either have the Right to Abode or Indefinite leave to remain in the UK or have the right of permanent residence in the UK under EC law. If the student’s passport describes them as a British citizen they have the Right of Abode.
  • Students with full Refugee status are eligible for fees and stipend.

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

 

Funding Details

The studentship covers full tuition fees and a tax-free stipend of £15,285 for four years starting in October 2020. Funding is only available to UK nationals and to EU nationals who have lived in the UK for three years prior to the start of the studentship.

How to apply

To apply please email Dr David Bevan with your CV, the contact details of two referees, and a covering letter.