OU secures £1.17m UKRI fellowship to explore extremal graph theory

The Open University (OU) has been awarded a prestigious £1.17 million Future Leaders Fellowship from UK Research and Innovation (UKRI) to lead groundbreaking research into extremal structures in graphs. The fellowship, awarded to Dr Katherine Staden from the OU’s School of Mathematics and Statistics, will advance fundamental mathematical theory with potential wide-ranging applications in artificial intelligence, networks, transport systems, and beyond.

Graphs – or networks – are abstract mathematical objects that underpin many aspects of modern life. From social media networks like Instagram, to the London Underground transport system or disease transmission modelling, graphs provide the framework for understanding connections between different entities. Beneath these real-world examples lies a mathematical structure: a graph, made up of vertices (points) and edges (lines), which captures how systems are linked.

Dr Staden’s fellowship focuses on the extremal properties of graphs, understanding their best- and worst-case behaviours. This branch of mathematics, known as extremal graph theory, asks fundamental questions such as: how can structures like Hamilton cycles (routes visiting every node exactly once) be found, counted, or decompose a host graph? These are not only theoretically rich challenges but also critical for designing efficient algorithms that support today’s vast and complex networks.

“Many graph problems are NP-complete, which means it is unlikely a quick algorithm exists to solve them at scale,” explains Dr Staden. “This makes it crucial to develop mathematical conditions that can guarantee specific properties and help us understand the behaviour of these networks. Extremal graph theory provides the tools to do just that.”

The research programme will follow two ambitious strands:

Counting structures in graphs

Addressing questions at the heart of extremal combinatorics, such as maximising or minimising the number of particular structures within a graph. This line of work connects deeply with major developments in the field, including the use of computers to produce rigorous mathematical proofs.

Graph decomposition 

Tackling one of the oldest and most enduring problems in discrete mathematics: how to partition a graph into prescribed pieces, such as Hamilton cycles. Beyond its theoretical depth, this area has practical applications in the design of statistical experiments and modern data science.

The award underlines the OU’s reputation for research excellence in mathematics and beyond. By combining deep theoretical inquiry with broad potential applicability, the fellowship showcases how OU researchers are shaping the foundations of future technologies, from AI systems to large-scale data analysis.

With funding of over £1.17 million from UKRI’s Future Leaders Fellowships: Round 9, this research will not only address questions that have challenged mathematicians for centuries but also help unlock new insights into the networks that shape our modern world.