Skip to main content

Grant success for Professor Stefanie Gerke

Grant success for Professor Stefanie Gerke

  • Date28 April 2022

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 Grant Success

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 ad­hoc 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.

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today