If you should ever find yourself having to organise a football tournament in which every team must play each other just once, here’s a tip: you don’t need to worry about the schedule until halfway through the contest.
That’s because – from a mathematical point of view – it doesn’t matter who plays whom during the first half for the schedule to work out; it’s only the second half of the tournament that needs careful planning.
That this is the case has only just been verified – and by mathematicians from the University. Professors Daniela Kühn and Deryk Osthus, Birmingham Fellows Dr Allan Lo and Dr Andrew Treglown, and their colleague Dr Béla Csaba, have stunned the world of extremal combinatorics by solving not just one long-standing problem, but three! Bearing in mind that ‘half-solving’ a problem in this area of mathematics is considered a feat, the results have been hailed as a major breakthrough.
The groundbreaking work was recently published in the Memoirs of the American Mathematical Society. Entitled ‘Proof of the 1-factorization and Hamilton decomposition conjectures’, it won the College’s Paper of the Month award.
The paper deals with the study of networks (also called graphs). One of the most famous classic examples in this field is the Travelling Salesman Problem (TSP). The more general area of Combinatorics – the study of finite or countable discrete structures – was until recently a small area within mathematics. But it’s grown rapidly and today is an established and very active field.
‘The kind of problems we are interested in are those that look at these networks and how they can be decomposed,’ explains Andrew. ‘So it’s breaking them into chunks; you’re interested in certain patterns. With the TSP, you’re interested in finding the cheapest, or most efficient, way of going through all the points and then returning to the original point exactly once. So we’re interested in breaking up our graphs into so called Hamilton cycles or so called “perfect matchings”.’
Perfect matching is when you have, say, a list of people on one side and a list of possible jobs they could do on the other – and deciding mathematically who is most suitable for which job.
Graph theory can be applied to many real-life situations, such as modelling social networks and networks and structures in biology, communications, computer science and genetics.
Following on from Daniela and Deryk’s breakthrough research on a related problem (which also has applications to the TSP), the team set about trying to solve three problems on graph decompositions – one dating from the 1950s and two from the 1970s.
The problems had clear connections, but it wasn’t immediately obvious that they could be solved at the same time: ‘On one level they look similar, but when you look at the detail, they are not,’ says Andrew.
‘What we did was to take a single approach to solve the three problems,’ Allan explains. ‘At one point we were concentrating on just two of them – so then it was a bit like “solve two and get the third free”! So it wasn’t like doing each one from scratch – it was using one approach and seeing how far we could take it.
‘Although the three problems fall into the same framework, we were surprised that we could use the one approach to get three results.
Roughly speaking, scheduling the second half of the football tournament mentioned before can be considered to be the 1-factorization problem. The Hamilton decomposition problem can be described by using the analogy of two islands close enough together to be connected by bridges. If, say, the weather was icy, how could you get all the roads on both islands, as well as the bridges between them, gritted without the vehicles having to go over the same ground more than once? Furthermore, you want each gritting vehicle to go through all the points and then returning to the original point exactly once.
Clearly, the routes are strongly depended on the layout of the network of roads and bridges. In one scenario, the islands each have dense networks of roads, but few bridges to the other island. In the opposite case, the islands’ internal road network is poor, but there are plenty of bridges between the two. Of course, the network may fall somewhere in between the two extremes.
‘The proof (of how to solve the problem) involves careful analysis of the two extreme cases,’ says Allan. ‘But it’s important to stress that you need to wait until the right tools come along – and it was a tool created by Daniela and Deryk that enabled us as a team to do what we did.
‘Also, you need to be very patient! This took us a couple of years to do, and it’s important to point out that because of the external grants won by Deryk and Daniela, who head the combinatorics group at Birmingham, that the group as a whole has the capacity to give all of us the time away from teaching in order to pursue our research. If we’d had to teach full-time, we wouldn’t have been able to do this.’
The increasingly collaborative nature of such research is also a key to solving some of mathematics’ most puzzling problems. ‘People imagine we work in isolation, in darkened rooms, but we don’t,’ says Andrew with a smile. Birmingham’s combinatorics group is one of the biggest in the world, comprising 18 members, eight of them permanent.
Still only in their early 30s, Allan and Andrew concede it’s unusual for such early-career researchers to achieve such success.
‘It’s good for our careers to have these results early on: most people wouldn’t get the opportunity to work on something this substantial, so we’re lucky to be part of the research group we have at Birmingham, which allows young people to work with more experienced Mathematicians on challenging problems.’
‘We see this as a stepping stone to bigger problems we are interested in,’ says Andrew, who did his first degree at Birmingham, as well as his PhD. ‘We now have a complete solution to one or shall we say three long-standing problems in graph theory, but there’s such a wealth of questions that still need answering. So now we are working on quite different questions – using different techniques and tools – but ones that are equally interesting.’
Allan adds: ‘What we have achieved so far motivates me to do more.’