Congratulations to Stefanie Gerke who, jointly with Paul Balister (University of Oxford), has been awarded a grant from the Engineering and Physical Sciences Research Council.
Professor Stefanie Gerke
Stefanie Gerke and Paul Balister (University of Oxford) have been awarded a grant to intensify their joint research on successive optimal structures.
Their project is in the area of probabilistic combinatorics, in particular probabilistic graph theory. The immediate connections of graphs to real world networks such as adhoc wireless networks, electrical grids, the internet, etc. and the abundance of interesting mathematical problems explain the attraction of this field.
Probabilistic combinatorics is one of the cornerstones of contemporary combinatorics and its methods are used widely in other branches of combinatorics (and beyond). Last year one of the Abel prizes was given to László Lovász partly for his work in probabilistic combinatorics and particularly his local lemma.
This project is concerned with robustness problems, which are a variant of resilience problems. Both problems have in common that one starts with a random graph and some edges respectively structures are removed deterministically/maliciously, and one still wants to find an object of interest.
An example of one model of random graphs of interest is the complete graph with random edge weights. Graphs where weights are associated with each edge have a wide variety of uses. For example, for a graph modelling a rail network, an edge weight could represent the travel time between a pair of stations, or one could look at a set of servers with the weights being the speed of a connection between a pair of servers.
In a complete graph on n vertices all the possible n(n − 1)/2 edges are present and in our model we will consider edge weights that are identically and independently distributed, say exponentially with expectation 1. This model is well studied. For example it is a celebrated result of Alan Frieze that as the number n of vertices tends to infinity, the total weight of the minimum spanning tree T tends in probability to zeta(3).
In this project, Paul Balister and Stefanie Gerke want to study what happens if one repeatedly removes best structures, for example shortest path or the cheapest matching, and looks at the next cheapest path or matching. Note that one has to investigate at most of the graph to find the best structure and therefore these parts are not random anymore when one considers the subsequent best structures which makes the problem far more complex.
