EPSRC Reference: 
EP/W015404/1 
Title: 
Successive Shortest Structures in Random Graphs 
Principal Investigator: 
Gerke, Professor S 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
Royal Holloway, Univ of London 
Scheme: 
Standard Research  NR1 
Starts: 
01 April 2022 
Ends: 
31 March 2023 
Value (£): 
74,171

EPSRC Research Topic Classifications: 
Logic & Combinatorics 
Statistics & Appl. Probability 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
We are surrounded by networks: Transport networks, social networks, infection networks, the internet, and electrical grids to name just a few. The natural way to model these kind of networks mathematically are graphs. Some networks, for example most transport networks, are rather static or develop slowly whereas many networks change fast and often in a manner that is hard to predict. To capture this unpredictable nature of networks one considers random graphs where each connection is chosen (independently) at random or, as in our project, one considers random weights on all possible connections. The research of random graphs does not only give us insights in realworld networks but also yields interesting and beautiful mathematics.
In this project we want to consider the effects of repeatedly removing structures from a complete graph with random edge weights. For example, we start with a network in which all connections are present and have a weight or length that is randomly distributed (independently from all the other weights). We have two special sites in our network and want to find the shortest path between them. With current methods that is easy to do as one can exploit the independence of the edges and can give a very precise prediction on the length of the path. When one removes this path and wants to find the next best path one cannot use the independence straight forwardly as one has already revealed most of the weights of the network when finding the first shortest path. In this project we investigate new approaches and methods to give very precise estimations on the length of the second shortest path, the third shortest path and so on. We also consider different structures to shortest paths to find common themes or differences.

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: 
