EPSRC Reference: 
EP/R022186/1 
Title: 
Random trees: analysis and applications 
Principal Investigator: 
Mailler, Dr CD 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematical Sciences 
Organisation: 
University of Bath 
Scheme: 
EPSRC Fellowship 
Starts: 
01 June 2018 
Ends: 
31 May 2021 
Value (£): 
281,510

EPSRC Research Topic Classifications: 
Statistics & Appl. Probability 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

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 interrelated parts, each of them is applicationdriven 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 twofold: 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 socalled "weighted random recursive tree", are used as a firststep 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 uptodate 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 socalled "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 nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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 