Until recently, combinatorics – the study of finite or countable discrete structures – was only a relatively small area within mathematics. Over the last few years, it has grown rapidly and today it is a well-established and very active field. Professor Deryk Osthus discusses the world leading Birmingham combinatorics study.
Following his Inaugural Lecture, Ros Dodd met Professor Deryk Osthus to find out more about the world-leading Birmingham combinatorics study.
Until recently, combinatorics – the study of finite or countable discrete structures – was only a relatively small area within mathematics. Over the last few years, it has grown rapidly and today it is a well-established and very active field.
It also has connections and applications to other disciplines, such as computer science and statistical physics. The internationally acclaimed work of Birmingham’s Professor Deryk Osthus and his long-standing colleague Professor Daniela Kühn in the School of Mathematics falls into this area. Between them they have solved problems that have baffled combinatorialists for half a century.
But it was the ‘beauty’ of combinatorics, a main feature of which is graph theory, that first attracted Deryk when he was a maths undergraduate at Cambridge.
‘I was drawn to it because it was beautiful maths; it is different and it is visual,’ he says. ‘I enjoyed these courses more than any other.’
Combinatorics has its origins in puzzles, such as the Four-Colour Theorem (which states that any map in a plane can be coloured using four colours in such a way that regions sharing a common boundary do not share the same colour), ‘which is surprising, and actually very hard to prove. Since the problems are sometimes puzzle-like, combinatorics is an area that may give the impression of being less deep than other parts of mathematics, but nowadays this is far from true.’
Although Deryk is a pure mathematician, he points out that graph theory has real-life applications.
‘For example, graph colouring has applications in scheduling, such as school timetabling, and in radio channel assignment.’
Deryk and Daniela are known for using ‘randomness’ to solve long-standing problems in combinatorics, and it was this that won them the European Prize in Combinatorics in 2003. On the surface, of course, randomness sounds entirely at odds with the preciseness of maths.
‘It does sound counter-intuitive at first,’ agrees Deryk.
But what you’re trying to do is to find a good solution to a problem and you don’t know how to do it. So you flip a coin to decide what the solution should look like. Then you can show, with high probability, that you will arrive at a solution that is pretty good – perhaps not the best, but good enough. So it’s not as random as it sounds.
In his recent inaugural lecture, entitled ‘Randomness to the rescue: if in doubt, flip a coin’, Deryk explained that graphs are very simple objects that can be used to model surprisingly complex structures – internet graphs, social networks and biological networks such as the brain. However, many of the problems arising from these models are too large to be handled directly and can’t be solved by today’s computers.
‘This is where the coin-flipping comes in. Firstly, a very successful approach to understanding the structure of complex networks such as the internet has been to model these networks by random graphs. By doing this, you can prove things about models and predict how they will grow. Secondly, randomised decisions are a surprisingly useful tool to solve problems that have resisted other approaches for decades.’
One problem Deryk and Daniela solved using this approach was Kelly’s Conjecture, a deep conjecture on cycles in graphs posed in 1968. Their method is quite general and can be applied to several other problems – for example, to find good solutions to the Travelling Salesman Problem, which asks the question: if you have a group of cities at various distances from each other, what is the shortest possible route a travelling salesman could take so he visited each city only once and returned to where he started?
More recently, Deryk and Daniela have solved the 1-Factorisation Conjecture – related to graph colouring – which was also first posed more than 50 years ago.
It has taken us three years and 200 pages, but we have proved this as a Birmingham team-of-five, which included two Birmingham Fellows, Daniela and me.
Together, these results have led to Deryk and Daniela being invited to give a joint talk at the International Congress of Mathematicians in Seoul later this year – one of the highest accolades a mathematician can receive.
Just as you don’t associate maths with randomness, so you don’t think of it as being a creative discipline. Again, Deryk explains this isn’t the case.
Often one problem turns out to be deeper than you thought or it leads to other things. Maths isn’t like Sudoku, where it follows the same recipe. One always needs to invent new things and be creative. In fact, what I do is more about being creative than making calculations.
Has working with Daniela – which he’s done since they did their PhDs (Deryk’s in theoretical computer science) at the Humboldt University of Berlin and University of Hamburg respectively – helped him to become more creative and to achieve what he might not have been able to do alone?
‘We both have our own way of thinking that creates a synergy, so, yes,’ he says.
