| 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: |
|
|
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
|
|
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 |