EPSRC logo

Details of Grant 

EPSRC Reference: EP/R022186/1
Title: Random trees: analysis and applications
Principal Investigator: Mailler, Dr CD
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Mathematical Sciences
Organisation: University of Bath
Scheme: EPSRC Fellowship
Starts: 01 June 2018 Ends: 31 May 2022 Value (£): 281,510
EPSRC Research Topic Classifications:
Statistics & Appl. Probability
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
23 Jan 2018 EPSRC Mathematical Sciences Fellowship Interviews January 2018 Announced
29 Nov 2017 EPSRC Mathematical Sciences Prioritisation Panel November 2017 Announced
Summary on Grant Application Form
Trees are a mathematical object that arise naturally in various contexts: for example, in computer science, search trees are widely use in databases as an efficient way to store and retrieve data, in biology, phylogenetic trees are key in understanding the evolution of species, and in network theory, trees are meaningful, tractable models for large networks.

This applied probability project focuses on several models of random trees that arise from applications to computer science and physics. The project is divided into three distinct but inter-related parts, each of them is application-driven and involves proving fundamental mathematical results about random trees.

Part A of the project focuses on a new model of random inputs for the satisfiability problem: random Boolean trees. The importance of this problem is two-fold: fundamentally, since it is closely related to the P vs. NP problem (one of the seven Millenium problems of the Clay Mathematics Institute), and practically, as it is related to finding efficient algorithms for very common industrial problems such as hardware and software verifications.

In Part B, results about the shape (profile) of the so-called "weighted random recursive tree", are used as a first-step towards understanding more intricate models for animal and human mobility. Understanding how humans move, for example in a city, is crucial when aiming at understanding more complex phenomena such as the transmission of epidemics. The model I will study in this project was introduced by physicists and fits data collected in a study of capuchin monkeys. Proving mathematical results about this random walk will thus enhance our fundamental knowledge base around animal and human mobility.

In Part C, random trees are a model for large networks such as the internet, or social networks. Because of their enormous size (in terms of numbers of routers for the internet, or number of users in social networks), and because of the fact that they constantly evolve with time, it is impossible to keep an up-to-date map of these networks, and there is thus a need for good mathematical models. Although trees contains no "loops" (or cycles), whereas networks typically do, random trees are meaningful models for networks, and the fact that they have no cycles make them more tractable than random graphs. Part C focuses on such a model, introduced by physicists: the so-called "preferential attachment tree with fitnesses" and aims at proving results about its larger hub (node with the most links) and about its shape (or "profile").
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bath.ac.uk